为什么在这段代码中时间复杂度为O(n)而不是O(n ^ 2)？

Question

为什么时间复杂度不是O(n ^ 2)而是O(n)？不是第一个循环是n时间,而第二个循环是相同的,所以它变成了O(n*n),这里有什么问题？

void f(int n){

     for( ; n>0; n/=2){
         int i;
         for(i=0; i<n; i++){
             printf("hey");
         }
     }
}

Answer 1

第一个循环不是n时间,第二个循环是同一个,所以它变成了O(n*n).

以上陈述是错误的,因为:

1. 外循环不运行n.(外循环运行O(log n)时间,但在这种情况下无关紧要.)
2. 对于内循环,循环数n随变化值的不同而不同.

为了获得此代码的时间复杂度,我们应该计算内循环体执行的总次数.

1. 显然,n对于每个值,内循环的主体执行次数n.
2. 值n由for外循环的语句确定.它从作为函数参数给出的值开始,并且每次执行外循环体时减半.

正如评论中已经说过的那样,因为n + n/2 + n/4 + n/8 + ... = 2n这个算法的时间复杂度是O(n).

对于一些更具体的数学证明:

找到一个整数k这样2^(k-1) < n <= 2^k.为此k:

1. 内环总数的下限是1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1 >= n - 1 ? ?(n).
2. 内环总数的上限是1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 4n - 1 ? O(n).

因此,内环的总数?(n)也是如此O(n).