我一直在與幾個人就這種嵌套 for 回圈演算法的時間復雜度進行辯論：
for (i=1;i<=n;i*=2){
for (j=1;j<=i;j ) {
// some O(1) operation
}
}
現在我相信演算法的復雜性是O(NlogN)，原因是外回圈的復雜性是O(logN)，內回圈的復雜性是O(N)。
然而，有幾個人計算出這個演算法的復雜性是O(N)使用一些涉及 AP/GP 的方法。
這個演算法的復雜性是多少？如果真的是O(N)，它背后的直覺是什么？
uj5u.com熱心網友回復：
外回圈有一個回圈變數 ??，它始終是 2 的冪。外回圈將進行 1 ?log 2 ??? 迭代。
外回圈的每次迭代，內回圈的主體執行次數與 ?? 的值一樣多。因此，總的來說，該內部主體的執行次數由以下總和表示：
2 0 2 1 ... 2 ?log 2 ???
這是一個幾何級數。這可以寫成封閉式公式：
(1 ? 2 1 ?log 2 ??? ) / (1 ? 2)
簡化：
2?2 ?log 2 ??? ? 1
并且因為取冪補償了對數，所以這是就 ?? 而言的線性數量級：
2?2 ?log 2 ??? - 1 = O(2?? - 1) = O(??)
直覺
這里的一個關鍵是對數和指數相互吸收。
為了感受一下，請注意無論 ?? 是 16、17、18、19、20 還是 31，外回圈的迭代次數都不會改變。在所有這些情況下，外回圈執行 5 次, 內回圈執行 1 2 4 8 16 = 31 次。與 ?? 為 16 時相比，僅當 ??翻倍時，外部迭代次數增加了 1 。結果是內部身體執行也大約翻了一番......所以這兩個“事件”真的齊頭并進......線性。
有關 ?? 的不同值，請參見下表：
| ?? | 體內執行次數 |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 3 |
| 4 | 7 |
| 5 | 7 |
| 6 | 7 |
| 7 | 7 |
| 8 | 15 |
| 9 | 15 |
| 10 | 15 |
| 11 | 15 |
| 12 | 15 |
| 13 | 15 |
| 14 | 15 |
| 15 | 15 |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/504616.html
上一篇：串列中的for回圈？