Java Big O表示3嵌套循环的log（n） [英] Java Big O notation of 3 nested loops of log(n)

问题描述

以下嵌套循环的Big O符号是什么？

What would the Big O notation be for the following nested loops?

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

我的想法是：
每个循环是 O（log2（n））所以它就像乘法一样简单

My thoughts are: each loop is O(log2(n)) so is it as simple as multiply

O(log2(n)) * O(log2(n)) * O(log2(n))  =  O(log2(n)^3)

推荐答案

是的，这是正确的。

一找出嵌套循环的大O复杂性的方法，它的边界不会立即相互依赖，就是从内到外工作。最里面的循环执行O（log n）工作。第二个循环运行O（log n）次并且每次都执行O（log n），因此它执行O（log ² n）工作。最后，最外面的循环运行O（log n）次并且O（log ² n）在每次迭代时起作用，因此完成的总工作量是O（log ³ n ）。

One way to figure out the big-O complexity of nested loops whose bounds do not immediately depend on one another is to work from the inside out. The innermost loop does O(log n) work. The second loop runs O(log n) times and does O(log n) work each time, so it does O(log² n) work. Finally, the outmost loop runs O(log n) times and does O(log² n) work on each iteration, so the total work done is O(log³ n).

希望这会有所帮助！

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