外层循环执行 log(n) 次的双 while 循环算法的渐近增长率

Question

这个算法的渐近增长率是多少（取决于n）？

i = 1; // executed 1 time
while( i ≤ n) {
    j = 1; // executed log(n) times

    while( j ≤ i) {
       j = j + 1; // ?
    }

    i = 2*i; // executed log(n) times
}

当 n 等于 10 时：

| i iterations | j itérations
| i=1          | j=1
| i=2          | j=1 j=2 
| i=4          | j=1 j=2 j=3 j=4
| i=8          | j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8

外层循环(i)执行了log(n)次

内循环(j)做作执行了多少次？

Answer 1

这应该是O(n)。

外循环的最后一次迭代有 n 次内循环迭代。外循环的倒数第二个迭代具有内循环的 n/2 次迭代。倒数第三次迭代具有 n/4:

n + n/2 + n/4 + ... = 2*n

请参阅 geometric progressions 了解计算总和的公式。

Answer 2

当n为4时，外层循环的最后一次执行导致内层循环执行了4次。当您将 n 从 4 加倍到 8 时，外循环将再执行一次，而在外循环的最后一次执行中，内循环将执行 8 次。再次加倍到 16，外循环将执行一次，内循环执行 16 次。因此，将输入加倍会导致执行时间加倍（加上另一个外部循环的时间，随着 n 变大，它变得微不足道）。

所以 O(n)。

外层循环执行 log(n) 次的双 while 循环算法的渐近增长率

Asymptotic growth rate of a double while loop algorithm with an outer loop executed log(n) times

algorithm

asymptotic-complexity