java - 下面代码的复杂度是多少？

Question

根据这段代码:

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-loop 将运行 log(n) 次， 起初我想到了 2n-1 作为第二个 for-loop，但它不适用于奇数。

有什么想法吗？ :)

Answer 1

• 当i = 1时，内循环会运行1次
• 当i = 2时，内循环会运行2次
• 当i = 4时，内循环会运行4次
• ...
• 当i = N时，内循环会运行N次

打印语句执行1 + ... + N/4 + N/2 + N 次，即O(n)。