嵌套循环的运行时分析

Question

也许是一个有点愚蠢的问题，但这段代码的运行时分析让我感到困惑。

int i, j; 
int k = 0;

for(i = 1; i<= n; i*= 2){
    for (j = 1; j <= i; j++){
    k += (i+j);
    }
 }

我知道外层循环运行时间将为 log(base2)n ，并且运行时间的总价值是外层循环的运行时间 * 内层循环的运行时间。我只是对内部循环有点困惑，我知道内部循环是根据 i 的值进行迭代的。那么内部循环运行时间也是 log(base2)n 那么整体运行时间将是 (log(base2)n)^2 吗？不知怎的，我觉得这不对。

Answer 1

代码有两个循环：

外环：

• 从 i=1 开始，每次将 i 乘以 2
• 当 i 大于 n 时停止
• 因此，它运行 log2(n) 次（因为重复乘以 2 与逆向除 n 除以 2 相同）。

内循环：

• 从 j=1 运行到 j=i
• 运行的次数取决于i的值
• 例如，如果i=4，则内循环运行4次

所以

• 当i=1时，内循环运行1次。
• 当i=2时，内循环运行2次。
• 当i=4时，内循环运行4次。
• 当i=8时，内循环运行8次。

这一直持续到 i 达到 n。

内循环的总迭代次数为：1+2+4+8+⋯+n

这意味着内循环运行 𝑂(𝑛) 将外循环中的所有工作加起来时的总次数。

整个代码的运行时间是𝑂(𝑛)，因为内循环主导了完成的总工作。