当迭代次数不恒定但迭代次数范围已知时，for 循环的大 O 时间复杂度

Question

据我所知，如果你有一个 for 循环，它的迭代次数为常数值，例如 1000，那么时间复杂度应该是 O(1)。但如果不知道迭代次数，而是留给用户输入，并且输入可以指定为任意数字，那么它就是 O(N)。

但是，如果不知道迭代次数，但是知道迭代次数的范围呢？比方说，100% 的时间范围在 10-28 次迭代之间。时间复杂度是 O(1) 还是 O(N)，为什么？

Answer 1

时间复杂度仍将被视为

O(1)

。迭代次数始终受固定常数限制，不依赖于输入大小。同样重要的是，时间复杂度取决于最坏的情况，在您的情况下是 28 次迭代，固定大小。