java - 具有嵌套循环的代码片段的 Big-O

<分区>

我们收到了一段代码来找到它的大O:

for(int i = 1;i ≤ n;i = 2 ∗ i)
    for(int j = 1;j ≤ i;j = 2 ∗ j)
        for(int k = 0; k ≤ j; k++)
             //do something elementary

第一行应该是 O(log(n)) 但第二行变得复杂，第三行更复杂。我最初认为第二行也可以是 O(logn) 但上限 j < i 可能会对此提出异议。任何帮助和解释将不胜感激!

最佳答案

这闻起来像家庭作业。没关系，我会试一试。

我的逻辑是第二级是 log(log n)，也许是 log(log n)/2。第三个将是 log(log(log n))。因此最终结果:

log(n) * log(log(n)) * log(log(log(n))).

据此我会说大 O 是 log(n)，因为这是最大的因素。

为什么:

第二个循环会迭代多少次。第一次迭代:i = 1, j = 1。它将循环 1 次。最后一次:i = n，会循环log(n)次。平均而言，它将循环 log(n)/2 次。所以我的直觉是错误的...

编辑:

第三个循环平均运行 n/2 次。

因此，总而言之，log(n)*log(n)n = nlog(n)^2。

但我知道什么!？

关于java - 具有嵌套循环的代码片段的 Big-O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36861580/

相关文章：

java - Java8 中使用多个键对映射列表进行排序