對於內部循環,存在一種情況,其中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
簡單地說,這兩個值的乘法不是? – Zermingore