循环分析——算法分析

Question

谁能分析一下练习6的字母b为什么是线性的？外循环似乎每次都将 i 增加 2 倍，所以我认为它是对数的...

来自link：

int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;

Answer 1

这是一个几何级数。内循环每次外循环迭代运行i次迭代，外循环每次减少一半。

所以，总结起来就是：

n + n/2 + n/4 + ... + 1

这是 geometric series，r=1/2 和 a=n - 收敛到 a/(1-r)=n/(1/2)=2n，所以：

T(n) <= 2n

并且由于 2n 在 O(n) - 算法以线性时间运行。

这是一个完美的例子，可以看出复杂性不是通过乘以每个嵌套循环的复杂性来实现的（这会让你 O(nlogn)），而是通过实际分析需要多少次迭代来实现。

Answer 2

是的，很简单看到n的值每次都减半，我运行s n次。

所以这是我第一次从 1 到 n 下次 0 到 n/2 因此第 k 项为 0 到 n/k。

现在内部循环的总时间将运行 = Log(n)

所以它是 GP，我的次数是运行ning。有条款

n,n/2,n/4,n/8....0

所以我们可以求出GP的总和

2^(long(n) +1)-1  / (2-1)

2^(long(n)+1) = n
hence n-1/(1) = >O(n)

Loop Analysis - Analysis of Algorithms