3个嵌套循环的大O. [英] Big O for 3 nested loops

问题描述

另一个大O符号问题...对于代码的大O是什么：

Another Big O notation question...What is the Big O for the folling code:

     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是正确的吗？

My Thoughts: So breaking it down, I think the outside loop is O(log2(n)), then each of the inner loops is O(n) which would result in O(n^2 * log2(n)) Question #1 is that correct?

问题＃2：
组合嵌套循环时，它总是像每个循环的大O一样简单吗？

Question #2: when combining nested loops is it always just as simple as mulitply the Big O of each loop?

推荐答案

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

When loop counters do not depend on one another, it's always possible to work from the inside outward.

最里面的循环总是花费时间O（n），因为无论j和i的值如何，它都会循环n次。

The innermost loop always takes time O(n), because it loops n times regardless of the values of j and i.

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

When the second loop runs, it runs for O(n) iterations, on each iteration doing O(n) work to run the innermost loop. This takes time O(n²).

最后，当外循环运行时，它会执行O（n ² ）每次迭代的工作。它也运行O（log n）次迭代，因为它的运行时间等于在达到1之前必须将n除以2的次数。因此，总工作量为O（n ² log n）。

Finally, when the outer loop runs, it does O(n²) work per iteration. It also runs for O(log n) iterations, since it runs equal to the number of times you have to divide n by two before you reach 1. Consequently, the total work is O(n² log n).

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

In general, you cannot just multiply loops together, since their bounds might depend on one another. In this case, though, since there is no dependency, the runtimes can just be multiplied. Hopefully the above reasoning sheds some light on why this is - it's because if you work from the inside out thinking about how much work each loop does and how many times it does it, the runtimes end up getting multiplied together.

希望这有帮助！

这篇关于3个嵌套循环的大O.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！