日志的3个嵌套循环的Java大O符号（N）(Java Big O notation of 3 nes

将大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（日志² 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大-O（n）和它嵌套因此通常O（N * N），它是O（n ^ 2）实际大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++;
         }
     }
}

这是嵌套循环，每个循环大O是O(log(n))这样一起复杂性是O(log(n)^3)

Answer 3:

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

文章来源: Java Big O notation of 3 nested loops of log(n)