java - 嵌套循环时间复杂度 for( i = n; i > 0; i/= 2) VS for( i = n; i > 0; i/=2) for( j = 0; j < i; j++)

Question

我无法找出算法 A 和算法 B 的时间复杂度，请帮助我!!!

算法A:

for(int i=n; i>=1; i/=2)
    some statement  

如果我没记错的话，

i = n;
i = n / 2 to the power of 1;
i = n / 2 to the power of 2;
i = n / 2 to the power of 3;
i = n / 2 to the power of 4;
.................
.................
i = n / 2 to the power k;

Algo A terminate when,

n / 2 to the power of k < 1
Therefore k = log n, Algo A take logn time;

算法B:

for(i=n; i>=1; i/=2)
   for(j=0; j<i; j++)
      some statement

伙计们，我无法找出算法 B 的时间复杂度，所以如何计算它并纠正我，如果我对算法 A 错了

Answer 1

简短回答:如果“某个语句”在恒定时间内运行，那么算法 B 的运行时间为O(n).

我们先分析一下内循环:

for(j=0; j<i; j++)
    some statement

自 j从 0 迭代(含)至i (独家)，这意味着它将因此执行 i操作。

现在我们可以分析外部部分:

for(i=n; i>=1; i/=2)
    // i operations

这里i因此以 n 开头，每次除以2 ，每次迭代，我们执行 i任务。

这意味着任务总数是:

 n + n/2 + n/4 + n/8 + ... + 1

以上是已知序列:

 m
---
\          -k           -m
/     n * 2     = (2 - 2  ) n
---
k=0

这里k因此范围从 0 到 log₂n，因此指令总数为 (2-2^{log< sub>2n})× n 或 (2 - 1/n)× n ，因此 2× n - 1 。我们可以将其简化为O(n)。