java - 3 个嵌套循环的大 O

Question

另一个大 O 表示法问题......以下代码的大 O 是什么：

     for (int i = n; i > 0; i = i / 2){
        for (int j = 0; j < n; j++){
           for (int k = 0; k < n; k++){
              count++;
           }
        }
     }

我的想法：所以分解它，我认为外部循环是O(log2(n))，那么每个内部循环O(n)都会导致O(n^2 * log2(n)) 问题 #1 是否正确？

问题 #2：当组合嵌套循环时，是否总是像将每个循环的 Big O 相乘一样简单？

Answer 1

当循环计数器不相互依赖时，总是可以从内向外工作。

最里面的循环总是花费时间 O(n)，因为不管 j 和 i 的值如何，它都会循环 n 次。

当第二个循环运行时，它会运行 O(n) 次迭代，每次迭代都做 O(n) 次工作以运行最里面的循环。这需要时间 O(n ² )。

最后，当外循环运行时，它每次迭代都会做 O(n ^{2 ) 的工作。}它还运行 O(log n) 次迭代，因为它运行的次数等于在达到 1 之前必须将 n 除以 2 的次数。因此，总工作量为 O(n ² log n)。

通常，您不能只是将循环相乘，因为它们的边界可能相互依赖。但是，在这种情况下，由于没有依赖关系，因此运行时可以成倍增加。希望上述推理能够解释为什么会这样——这是因为如果你从内到外思考每个循环做了多少工作以及它做了多少次，运行时最终会成倍增加。

希望这可以帮助！

Answer 2

1. 是的，这是正确的：外部循环是logN，另外两个是N每个，总共O(N^2*LogN)
2. 在简单的情况下，是的。在更复杂的情况下，当循环索引从其他索引指示的数字开始时，计算会更复杂。

Answer 3

为了更正式地回答这个问题（注意：稍微），比如说T(n)完成算法所需的时间（或操作次数）。然后，对于外循环，T(n) = log n*T2(n)，其中T2(n)是循环内的操作数（忽略任何常数）。类似地，T2(n) = n*T3(n) = n*n。

然后，使用以下定理：

若f ₁ (n) = O(g ₁ (n))且f ₂ (n) = O(g ₂ (n))，则f ₁ (n)×f ₂ (n) = O(g ₁ (n ) )×g ₂ (n))
（来源和证明）

这给我们留下了 T(n) = O(n ² logn)。

“组合嵌套循环”只是这个定理的一个应用。问题在于准确计算每个循环使用了多少操作，在这种情况下这很简单。

Answer 4

您可以使用 Sigma Notation 正式进行，以忠实地模仿您的循环：