时间戳

首页 > 解决方案 > 为什么这段代码的时间复杂度是 O(n) 而不是 O(n^2)？

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

问题描述

为什么这里的时间复杂度不是 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");
         }
     }
}

标签： cloopstime-complexitybig-ocomplexity-theory

解决方案

不是第一个循环是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)。

推荐阅读