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: 组合嵌套循环时，是否总是像将每个循环的大 O 相乘一样简单？

Answer 1

当循环计数器彼此不依赖时，总是可以从内到外工作。

最内层的循环总是花费时间 O(n)，因为无论 j 和 i 的值如何，它都会循环 n 次。

当第二个循环运行时，它运行 O(n) 次迭代，在每次迭代中执行 O(n) 次工作以运行最内层循环。这需要时间 O(n²)。

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

一般来说，您不能只将循环相乘，因为它们的边界可能相互依赖。但是，在这种情况下，由于没有依赖性，运行时间可以成倍增加。希望上面的推理能说明为什么会这样 - 这是因为如果你从内到外思考每个循环做了多少工作以及它做了多少次，运行时间最终会成倍增加。

希望这对您有所帮助!