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

最佳答案

第一个循环不是n次,第二个循环也是,所以它变成O(n*n)
上述陈述是错误的,因为:
外部循环不运行n次。(外部循环运行O(log n)次,但在这种情况下无关紧要。)
对于内部循环,循环数随n值的变化而变化。
为了获得这个代码的时间复杂度,我们应该计算内部循环的主体执行的次数。
显然,对于n的每个值,内部循环的主体都要执行n次。
n的值由外部循环的for语句确定。它从作为函数参数给定的值开始,并且每次执行外部循环的主体时减半。
如评论所述,自n + n/2 + n/4 + n/8 + ... = 2n以来,该算法的时间复杂度为O(n)
关于这一点的更具体的数学证明:
找到一个整数。对于这个k
内循环总数的下限是2^(k-1) < n <= 2^k
内环总数的上限是k
因此,内环的总数是1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1 >= n - 1 ∈ Ω(n)1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 4n - 1 ∈ O(n)

关于c - 为什么在此代码中时间复杂度为O(n)而不是O(n ^ 2)?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51163614/

10-11 16:41