algorithm - 循环分析——算法分析

Question

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

有人可以分解为什么练习 6 字母 b 是线性的吗？外循环似乎每次都将 i 增加 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

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

T(n) <= 2n

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

---

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