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).

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

希望这可以帮助!