为什么这段代码的时间复杂度是 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

Isn't the first loop is n times, & the same is the second one, so it becomes O(n*n).

以上说法是错误的，因为：

1. 外层循环没有运行n次。 （外层循环运行s 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)。