具有连接变量的环的两个循环的时间复杂度计算

Question

的时间是什么：

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

为此，我认为是
1.外循环将运行logn Time
2.内部循环也将运行logn时间。
因为我认为内部循环j与k有关。因此，k运行多少，也是J的运行时间。
So Total = O（logn * logn）

，但在文本中，他们给出了总= o（2n-1）。
你能解释一下

Answer 1

当k为1（sum ）运行1次

当k为2（sum ）运行2次

k是4（sum ）运行4次

当k为n = 2^k（sum ）运行2^k次

所以我们必须计算

1 2 4 ... 2^k = 2^0 2^1 2^2 .... 2^k =（1-2^（k 1））/（1-2）

因为我们将n = 2^k so：

放在

k = log（n）

2^（log（n））= n^（log（log（2））

2* 2^k -1 = 2* n -1

Answer 2

最容易解释此问题，因为忘记了外循环在那里，并首先查看内部循环复杂性。假设内部循环运行" M"时间...然后将" sum "操作的总数为

1 2 4 ... 2^（M-1）

通过注意到这是由所有1组成的二进制数，可以将此总和减少到'2^（m）-1'。现在问题是m？您已经弄清楚了，m = log（n） 1（ 1是因为循环必须至少运行一次）。将其插入内部循环复杂性中，

2^（log（n） 1）-1 = 2*n -1。

因此，整个环将缩放为O（2N-1）。希望这会有所帮助！