java - 3 个 log(n) 嵌套循环的 Java Big O 表示法

Question

以下嵌套循环的大 O 表示法是什么？

     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))如此简单，就像乘法一样简单

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

Answer 1

对，那是正确的。

找出边界不立即相互依赖的嵌套循环的大 O 复杂性的一种方法是从内向外工作。最里面的循环做 O(log n) 工作。第二个循环运行 O(log n) 次并且每次都运行 O(log n)，所以它运行 O(log ² n)。最后，最外面的循环运行 O(log n) 次，每次迭代都做 O(log ² n) 工作，所以完成的总工作是 O(log ³ n)。

希望这可以帮助！

Answer 2

是的你是对的。

简单的计算方法——

for(int i=0; i<n;i++){ // n times 
    for(int j=0; j<n;j++){ // n times
    }
}

这个简单嵌套循环的例子。这里每个循环 O(n) 的 Big-O 并且它是嵌套的，因此通常是 O(n * n)，这是 O(n^2) 实际的 Big-O。在你的情况下 -

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

在嵌套循环中，每个循环 Big-O 都是O(log(n))如此，复杂性将是O(log(n)^3)

Answer 3

确实，你的假设是正确的。您可以像下面这样有条​​不紊地展示它：