嵌套循環的算法複雜性的一些例子？

Question

我已經看到，在某些情況下，嵌套循環的複雜度爲O（n^2），但我想知道在什麼情況下，我們可以有嵌套循環以下的複雜性：

• 爲O（n）
• O（log n）我在某處看到過這種情況，但我不記得確切的例子。

我的意思是有任何一種公式或技巧來計算嵌套循環的複雜性？有時當我應用總和公式時，我沒有得到正確的答案。

一些例子會很好，謝謝。

Answer 1

這是給你一個例子，其中的時間複雜度爲O（n），但你有一個雙循環：

int cnt = 0; 
for (int i = N; i > 0; i /= 2) { 
    for (int j = 0; j < i; j++) { 
     cnt += 1; 
    } 
} 

您可以通過以下方式證明了複雜性：

第一迭代，j循環運行N次。第二次迭代，j循環運行N/2次。第i次迭代，j循環運行N/2^i次。 所以總：N * (1 + 1/2 + 1/4 + 1/8 + …) < 2 * N = O(N)

---

這將是誘人的說，像這樣運行在O(log(n))：

int cnt = 0; 
for (int i = 1; i < N; i *= 2) { 
    for (int j = 1; j < i; j*= 2) { 
     cnt += 1; 
    } 
} 

但我相信，這將運行在O(log^2(N))這是polylogarithmic