嵌套循环的算法复杂性的一些例子？

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