以下代码的复杂度是多少？

Question

4

根据这段代码：

for (int i=1; i<=N; i*=2)
{
  for (int j=1;j<=i;j++)
  {
    System.out.println("The value for i is "+i+" and the value for j is "+j);
  }
}

第一个for循环将运行log(n)次，一开始我想用2n-1来代替第二个for循环，但对于奇数不起作用。

有什么想法？ :)

- user3813409

这是第一个循环执行的次数（log(n)）乘以第二个循环执行的次数（i）的总和。 - Charlie

你想要渐进复杂度还是迭代次数？渐进复杂度是n*log(n)。 - Tim Seguine

我需要考虑每行的迭代次数，然后找出 O 表示法。 - user3813409

2个回答

2

您的第一个for循环将i作为一系列:

enter image description here

第一个循环在此系列的最后一个元素大于或等于N时停止:

enter image description here

x代表第一个循环执行的次数。现在我们正在尝试找到x:

enter image description here

其中

enter image description here

是的，就像您所说的那样:

第一个for循环将运行log(n)次

第二个for循环体作为总和运行:

enter image description here

这证明了您的算法具有O(n)复杂度

如果N是以下之一，则会打印2N-1次：1, 2, 4, 8, ... , 2^n

这只是表面分析，但它做到了。

- Everettss

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maroun · Accepted Answer

打印语句将会被执行1 + ... + N/4 + N/2 + N次，这是O(n)的。