Java Big O表示3嵌套循环的log（n）

对于以下嵌套循环，Big 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 

这个简单嵌套循环的例子。 这里每个循环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

的确，你的假设是正确的。 您可以有条不紊地显示它，如下所示：