这个算法是O(1)吗？

Question

以下算法是简单的O(1),还是其复杂性难以定义？

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

当n <= 10时,我很惊讶它显然是O(n).

Answer 1

它是O(1),因为无论输入(n)的大小如何,它都需要恒定的时间.当n <= 10时,将其称为O(n)是没有意义的,因为大哦符号是根据渐近函数增长来定义的,即,对于n"大",或者大于某个值.这是因为n的实际值与渐近复杂度无关:它是一种将不同算法相互比较的方法.

看看big-oh 的定义:函数f(n)是O(g(n))如果存在常数c> 0且正整数m使得f(n)<c*g( n)对于n> m.在你的情况下,f(n)是运行算法所需的时间,g(n)= 1,m = 10,c与循环10个整数所需的时间成正比.