问题

for (int i = 1; i < n; i++) {
   for (int j = 1; j < i; j *= 2) {
     //statement
   }
}
Answer: O(nlogn)

英文:

for (int i = 1; i &lt; n; i *= 2) {
   for (int j = 0; j &lt; i; j++) {
     //statement
   }
}
Answer: O(N)

I want to know what is the time complexity if the inner loop and the outer loop are reversed ,O(n), O(nlogn) or O(logn)?

for (int i = 1; i &lt; n; i ++) {
   for (int j = 1; j &lt; i; j *= 2) {
     //statement
   }
}
Answer: ?

答案1

得分: 1

在第二个例子中，内部循环将对每个n的值执行，因此我们需要对对数值求和。

让我们假设我们的底数是2。

log2(1) + log2(2) + log2(3) ... + log2(n-1)
= log2((n-1)!)

因此，复杂度将是O(log2((n-1)!))，这是以2为底的n-1的阶乘的对数。

如果省略2，它将是O(log((n-1)!))。

事实证明，您可以进一步简化，使用Stirling逼近得到答案O(nlogn)。

英文:

In the second example, the inner loop will execute for every value of n thus we need to sum logarithmic values.

Let's assume our base is 2.

log2(1) + log2(2) + log2(3) ... + log2(n-1)
= log2((n-1)!)

So the complexity would be O(log2((n-1)!)) which is the factorial of n-1 in log 2 base.

And if you omit 2 it is O(log((n-1)!))

Turns out you can simplify further using Stirling's approximation and come with the answer O(nlogn).

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。