嵌套while循環的算法複雜性

Question

所以我在這個問題上有點麻煩，因爲變量i。我只是不確定如何在第二個while循環中處理它。對於我的外循環，我明白它會運行log_4（n^2）迭代。對於內部while循環，我計算了迭代次數爲（2n^3 - 3）/ i。我只是在努力如何將這兩者結合起來以獲得這個功能的總體複雜性。任何輸入，非常感謝！

function p(n) 
    i = 1; 
    while i < n^2 do 
     j = 3; 
     while j < 2n^3 do 
      j = j + i; 
     end 
     i = 4i; 
    end 

Answer 1

我不善於數學，但我試圖回答這個問題。

首先，讓我們從第一次迭代計數：

• I = 1：j被約2N^3倍增加（常數可以忽略分析複雜時）
• i = 4的：j被增加約2n^3/4次
• i = 16：j增加約2n^3/16次。
• ...
• i = n^2：j增加約2n^3 /（n^2）次。

在總j被增加： （2N^3）+（2N^3）/ 4 +（2N^3）/ 16 +（2N^3）/ 64 + ... +（2N^3）/（n^2）次。 即：

2n^3*(1+1/4+1/16+1/64+1/256+...+1/(n^2)) 
= 2n^3((1-(1/4)^(log_4(n^2)))/(1-(1/4))) // sum of geometric progression 
= 2n^3 * (1-1/n^2) * 4/3 

所以這是O（n^3）。

Answer 2

對於內部循環，存在一種情況，其中i = 1，一旦開始。 對於i = 1，內部循環有大約2n^3次迭代，我們可以說第一次外部循環的複雜度是O（n^3）。

請注意，由於我們試圖計算複雜性，我將擺脫常數和係數。那麼，對於i的其他值，內循環的迭代次數約爲n^3/i。所以，當我增長時，迭代的次數會急劇減少。最後，對於i〜= n^2的最後一個值，它將是n。

所以，現在，我們有一個像n^3 + ..... + n，這給了我們總的複雜性。 這個總和中的術語數是log_4（n^2）= 2log_4（n），比如log_4（n）。

通常，我們知道n^3 + n^2 + n與n^3相同。但問題是我們在這種情況下可以想到同樣的情況嗎？因爲在這種情況下，有更多的術語和術語數取決於n。讓我們來看看。

即使所有術語都是n^3種類，結果也會是log_4（n）* n^3。 但是在本系列中，其他條款的幾何下降值不會保持n^3。另外log_4（n）對於人們通常使用的大量數字來說是非常小的值。實際上，人們不能簡單地忽略它，但是當我們一起考慮它是一個小數字和其他術語「急劇下降;你可以忽略log_4（n）和我們可以說複雜度是O（n^3）。

這不是一個確切的數學解決方案，但爲了方便您，我們可以使用這種估算方法，如果您確定我們正在做什麼。這就是我的觀點，爲什麼我要這樣解釋。

如果你正在尋找更具體的東西，你可以說它介於O（n^3）和O（log_4（n）* n^3）之間。

此外，我已經計算了一些不同n值的實驗值。您可以看到數字在代碼中的行爲，以及迭代次數與n^3之間的關係。以下是結果：

Test #1: 
n: 15 
n^2: 225, n^3: 3375 
...i=1, added 3375 iterations 
...i=4, added 843 iterations 
...i=16, added 210 iterations 
...i=64, added 52 iterations 
Total # of iterations for this test case: 4480 

Test #2: 
n: 56 
n^2: 3136, n^3: 175616 
...i=1, added 175616 iterations 
...i=4, added 43904 iterations 
...i=16, added 10976 iterations 
...i=64, added 2744 iterations 
...i=256, added 686 iterations 
...i=1024, added 171 iterations 
Total # of iterations for this test case: 234097 

Test #3: 
n: 136 
n^2: 18496, n^3: 2515456 
...i=1, added 2515456 iterations 
...i=4, added 628864 iterations 
...i=16, added 157216 iterations 
...i=64, added 39304 iterations 
...i=256, added 9826 iterations 
...i=1024, added 2456 iterations 
...i=4096, added 614 iterations 
...i=16384, added 153 iterations 
Total # of iterations for this test case: 3353889 

Test #4: 
n: 678 
n^2: 459684, n^3: 311665752 
...i=1, added 311665752 iterations 
...i=4, added 77916438 iterations 
...i=16, added 19479109 iterations 
...i=64, added 4869777 iterations 
...i=256, added 1217444 iterations 
...i=1024, added 304361 iterations 
...i=4096, added 76090 iterations 
...i=16384, added 19022 iterations 
...i=65536, added 4755 iterations 
...i=262144, added 1188 iterations 
Total # of iterations for this test case: 415553936 

Test #5: 
n: 2077 
n^2: 4313929, n^3: 8960030533 
...i=1, added 8960030533 iterations 
...i=4, added 2240007633 iterations 
...i=16, added 560001908 iterations 
...i=64, added 140000477 iterations 
...i=256, added 35000119 iterations 
...i=1024, added 8750029 iterations 
...i=4096, added 2187507 iterations 
...i=16384, added 546876 iterations 
...i=65536, added 136719 iterations 
...i=262144, added 34179 iterations 
...i=1048576, added 8544 iterations 
...i=4194304, added 2136 iterations 
Total # of iterations for this test case: 11946706660 

Test #6: 
n: 5601 
n^2: 31371201, n^3: 175710096801 
...i=1, added 175710096801 iterations 
...i=4, added 43927524200 iterations 
...i=16, added 10981881050 iterations 
...i=64, added 2745470262 iterations 
...i=256, added 686367565 iterations 
...i=1024, added 171591891 iterations 
...i=4096, added 42897972 iterations 
...i=16384, added 10724493 iterations 
...i=65536, added 2681123 iterations 
...i=262144, added 670280 iterations 
...i=1048576, added 167570 iterations 
...i=4194304, added 41892 iterations 
...i=16777216, added 10473 iterations 
Total # of iterations for this test case: 234280125572 

Test #7: 
n: 11980 
n^2: 143520400, n^3: 1719374392000 
...i=1, added 1719374392000 iterations 
...i=4, added 429843598000 iterations 
...i=16, added 107460899500 iterations 
...i=64, added 26865224875 iterations 
...i=256, added 6716306218 iterations 
...i=1024, added 1679076554 iterations 
...i=4096, added 419769138 iterations 
...i=16384, added 104942284 iterations 
...i=65536, added 26235571 iterations 
...i=262144, added 6558892 iterations 
...i=1048576, added 1639723 iterations 
...i=4194304, added 409930 iterations 
...i=16777216, added 102482 iterations 
...i=67108864, added 25620 iterations 
Total # of iterations for this test case: 2292499180787