依赖嵌套for循环的时间复杂度？

Question

你能解释一下如何找到时间复杂度吗？

sum=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=k;j++)
     sum++;

所以,我知道外部循环的时间复杂度为O(logn),但由于内部循环的迭代取决于外部循环的值,因此该算法的复杂性不是O(nlogn).

这本书说它是O(n).

我真的不明白它是怎么样的O(n)......有人可以解释一下......如果你能详细说明,我将非常感激btw:D

数学解决方案可以帮助我更好地理解......

Answer 1

只需看看内循环运行的次数:

1 + 2 + 4 + 8 + 16 +...+ n

请注意,如果n = 32,那么这个sum = 31 + 32. ~ 2n.
这是因为除了最后一个术语之外的所有术语的总和几乎等于最后一个术语.

因此整体复杂性= O(n).

编辑:

几何级数和(http://www.mathsisfun.com/algebra/sequences-sums-geometric.html)的顺序为:

(2^(logn) - 1)/(2-1) = n-1.

Answer 2

外层循环执行log(Base2)n次，所以时间复杂度为O(log(Base2)n)。

内部循环对于外部循环的每次迭代执行 k 次。现在，在外部循环的每次迭代中，k 递增到 k*2。

所以内循环迭代总数=1+2+4+8+...+2^(log(Base2)n)
=2^0+2^1+2^2+...+2^log( Base2)n (几何级数)
=2^((log(base2)n+1)-1/(2-1)
=2n-1.
=O(n)
所以内循环是 O(n). 所以总计时间复杂度=O(n)，即O(n+log(base2)n)=O(n)。

更新：它也是 O(nlogn) 因为 nlogn>>n 对于较大的 n 值，但它不是渐近紧的。你可以说它是 o(nlogn)[Small o] 。