依赖嵌套循环上的大 O 复杂性

Question

我可以在理解如何解决本教程问题方面获得一些帮助吗？我仍然不明白我的教授的解释。我不确定如何计算第三个/最内部循环的大 0。她解释说，这个算法的答案是O（n^2），第二个和第三个循环必须被视为一个循环，O（n）的大0。有人可以向我解释一下第二/第三循环的大 O 符号吗，用基本的外行术语假设 n = 2^m

for ( int i = n; i > 0; i --) {     
  for (int j =1; j < n; j *= 2){
        for (int k =0; k < j; k++){
        }
  }
 }

据我了解，第一个循环有一个大的 O 表示法 O（n）第二个循环 = log（n）第三个循环 = log （n） （因为它将被循环的次数已经减少了 logn） * 2^（2^m-1）（ 来表示 j 的增加？

Answer 1

让我们将 print 语句添加到最里面的循环中。

for (int j =1; j < n; j *= 2){
        for (int k =0; k < j; k++){
            print(1)
        }
}

的输出

j = 1 ， 1 1

j = 2 ， 1 1 1

j = 4 ， 1 1 1 1 1

。

j = n，1 1 1 1 1 ... n+1次。

问题归结为这将打印多少1。

这个数字是

(2^0 + 1) + (2^1 + 1) + (2^2 + 1) + ... + (n + 1)

= (2^0 + 1) + (2^1 + 1) + (2^2 + 1) + ... + (n + 1)

= log n + (1 + 2 + 4 + ... + n)

= O(log n + n)

= O(n) .

---

假设你知道为什么(1 + 2 + 4 + ... + n) = O(n)

Answer 2

O-notation 是一个上限。你可以说它有 O（n^2）。对于最低上限，我认为它应该是属于O(n^2)的O(n*log(n)*log(n))。

Answer 3

这是因为对数。如果你有 log（16） 的幂 2 是 16。所以 log（n） 提高到 2 的幂是 n。这就是为什么你的老师说要把第二个和第三个循环一起看成O（n）。

如果第二个循环的最大迭代次数为 O（log（n）），则第二个和第三个循环将为：

Answer 4

for ( int i = n; i > 0; i --) {   // This runs n times  
  for (int j =1; j < n; j *= 2){  // This runs atmost log(n) times, i.e m times.
        for (int k =0; k < j; k++){  // This will run atmost m times, when the value of j is m.
        }
  }
 }  

因此，正如问题下的评论所述，总体复杂性将是所有三者的产物。
上限可以是宽松的，也可以是紧的。
你可以说它是loosely bound under O(n^2)或tightly bound under O(n * m^2).