循环分析-算法分析

Question

此问题基于此资源http://algs4.cs.princeton.edu/14analysis。

有人能分解为什么练习6字母b是线性的吗？外循环似乎每次增加2倍，所以我假设它是对数的.

从链接中：

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

这是几何级数，有r=1/2和a=n，它可以收敛到a/(1-r)=n/(1/2)=2n，所以：

T(n) <= 2n

由于2n在O(n)中，所以该算法在线性时间内运行。

这是一个很好的例子，可以看到复杂性不是通过将每个嵌套循环的复杂性乘以(这会得到O(nlogn))实现的，而是通过实际分析需要多少迭代来实现的。

Answer 2

是的，简单地看，n的值每次减少一半，我运行n次。

因此，我第一次从1到n，下一次，从0到n/2，因此，在kth项上，从0到n/k。

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

所以这是一个GP，我运行的次数。有条件

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)