这个算法的时间复杂度是O(1)吗？

Question

以下算法的复杂度是简单的O(1)，还是其复杂度更加棘手？

这个算法的复杂度是简单的O(1)，不需要太多的计算。

for (i = 0; i < n; ++i)
    if (i > 10)
        break;

当 n <= 10 时，这显然是一个 O(n) 的复杂度，但我感到困惑。

- Egor Tensin

---

http://en.wikipedia.org/wiki/Asymptote。它是O(1)的，因为它是一个时间恒定的操作。 - Mephy

由于for循环在i>10时终止，它只循环了一个常数次数（即与n无关），因此运行时间为O(1)。 - chiwangc

我明白了，谢谢大家！ - Egor Tensin

循环语句有些具有欺骗性，因为通常这种类型的循环意味着O(n)。然而，if语句确保了一个约束条件。它永远不会超过10。10是一个常数，因此它是O(1)。顺便说一句，问得好。 - But I'm Not A Wrapper Class

Answer 1

它的时间复杂度为O(1)，因为它花费的时间是恒定的，不管输入的大小(n)。当n<=10时说它的时间复杂度是O(n)是没有意义的，因为大O符号是根据渐近函数增长来定义的，即对于"大"的n，或者比某个值更大的n。这是因为实际的n值对于渐近复杂度并不重要：它是一种将不同算法相互比较的方法。

只需要看一下big-oh的definition：如果存在常数c>0和正整数m，使得f(n)m，则函数f(n)是O(g(n))。在你的情况下，f(n)是运行算法所需的时间，g(n)=1，m=10，c与循环遍历10个整数所需的时间成比例。

- Giovanni Botta

Answer 2

是的，它是O(1)的。这意味着一个函数的时间复杂度为O(1)，也可以说它是有界的。那段代码的运行时间是有限制的，因此它是O(1)。

- alonamaloh