具有外循環的double while循環算法的漸近增長率執行log（n）次

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 

外環（ⅰ）做作被執行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變大而變得微不足道）。

So O（n）。