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

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

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

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

这本书说它是O(n).

我真的不明白它是如何O(n)…有人可以解释一下……
如果你能详细说明,我将非常感激：D

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

外循环执行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 (geometric series)
= 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)[小o].