java - 为什么这个算法是线性的而不是线性的？

Question

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

我很确定它会在 nlogn 中增长，但被告知它是线性的……为什么它是线性的而不是线性的？

Answer 1

它是线性的。想象一下n是 64 秒。内部循环运行 64 次，然后是 32 次，然后是 16 次，然后是 8 次，然后是 4 次，然后是 2 次，然后是 1 次。64 + 32 + 16 + 8 + 4 + 2 + 1 = 127。

所以它需要2n-1总操作（对于 2 的幂，但这不会改变分析），假设内部循环没有被优化掉。这很明显O(n)——线性的。

如果内部 for 循环被优化掉（到sum += n;），它是对数的。

Answer 2

该算法的复杂度为 Θ(N)。

操作次数为

sum{2**k} for k = 0..log2(N)

这个进度的总和是

2*N-1

这是Θ（N）。

Answer 3

形式上，使用 Sigma 表示法可以帮助您清楚地看到增长顺序是线性的。