Java Big O表示3嵌套循环的log(n)

发布时间：2020-12-14 16:18:44 所属栏目：Java 来源：网络整理

导读：对于以下嵌套循环,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(

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

解决方法

对,那是正确的.

找出嵌套循环的大O复杂性的一种方法是从内到外工作,这些嵌套循环的边界不会立即相互依赖.最里面的循环执行O(log n)工作.第二个循环运行O(log n)次并且每次都执行O(log n),因此它执行O(log2 n)工作.最后,最外面的循环运行O(log n)次并且O(log2 n)在每次迭代时都起作用,因此完成的总工作量是O(log3 n).

希望这可以帮助！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!