gpt4 book ai didi

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

转载 作者:太空宇宙 更新时间:2023-11-04 05:33:26 24 4
gpt4 key购买 nike

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

最佳答案

Isn't the first loop is n times, & the same is the second one, so it becomes 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) .

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

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com