Java代码的时间复杂度

Question

我正在Coursera学习算法课程，但是我卡在了这个问题上。我的任务是找到此代码的时间复杂度。

int sum = 0

 for (int i = 1; i <= N*N; i = i*2)

  {
     for (int j = 0; j < i; j++)
           sum++; 
  }

我在Eclipse中检查了这个问题，无论N的值是多少，sum语句执行的次数都小于N。

final value of sum:
for N=8 sum=3 
for N=16 sum=7 
for N=100000 sum=511

因此时间复杂度应该小于N，但给出的答案是N的平方，这可能怎么实现呢？

到目前为止，我所做的是：

第一个循环将运行log(N^2)次，因此第二个循环将执行1、2、3.. 2 logN次。

- Max

---

为什么你需要那个内部循环？干嘛不直接使用 sum += i？ - user207421

Answer 1

第一个内部循环将为1 + 2 + 4 + 8 .. 2^M，其中2^M <= N * N。

总和最多为N * N的2的幂次方之和约为2 * N * N或O(N ^ 2)。

注意：当N = 100000时，N * N会溢出，因此其结果是误导性的。如果您考虑溢出是问题的一部分，则对于大量数据而言，总和相当随机，因此您可以认为它是O(1)，即如果N = 2^15，则N ^ 2 = 2^30并且总和将为Integer.MAX_VALUE。没有更高的N值会给出更高的总和。

- Peter Lawrey

---

尝试在优化器中运行代码，确保它是 O(1)。 - huseyin tugrul buyukisik

请解释一下 1 + 2 + 4 + 8 .. 2^M (N^2) 的含义。 - Max

2的幂次方加起来直到2^M，其和为2^(M+1) - 1。我在高中时知道这个证明，但现在并没有太多用处。;) 如果你尝试一下，就可以看出这个规律。1、3、7、15、31、63、127、255等。 - Peter Lawrey

是的，M的值为log N^2，而2^(log N^2)则等于N^2。我希望这是正确的。 - Max

使用日志似乎是有道理的，直到Saeed指出它是错误的。我意识到2的幂之和基本上就是2 * 最大值，即N^2，因此时间复杂度为O(N^2)。对数并不涉及其中。 - Peter Lawrey

@tuğrulbüyükışık，它绝对不是O(1)。 - user207421

Answer 2

这里有很多混淆，但重要的是Big-O符号关注的是增长率或数学家所说的极限行为。函数以O(n*n)的执行意味着执行时间将比例如n快，但比如2^n慢。当使用big-O符号进行推理时，请记住常数“不算在内”。在这个问题中还有一些怪癖。

• 如果循环是一个常规的for循环，那么N*N表达式本身会导致O(log n*n)的复杂度...
• ...然而，for循环的增量是i = i*2，导致外部循环大约执行log n次，如果内部循环的内容与n无关，则函数的时间复杂度会是O(log n)。
• 但是，内部循环的运行时间又依赖于n，但它并不会执行n*n次循环，而是大约执行log (n*n)/2次循环。记住“常数不算”这一点，最终时间复杂度为O(n*n)。

希望这能澄清事情。

- vidstige

---

不对，for循环是i *= 2，而不是i *= i。 - nhahtdh

循环增量不是 i*=i，而是 i*=2。 - Gir

你的解释是不正确的。如果内部循环是O(1)（与n无关），那么外部循环将以O(log(n))运行。 - nhahtdh

Answer 3

因此，sum ++将被执行1 + 2 + 4 + 8 + ... + N*N，总共log2(N*N)次。几何级数之和为1 * (1 - 2 ^ log2(N*N)/(1 - 2) = O(N*N)。

- Roman Dzhabarov

Answer 4

你的外层循环是log(N^2)->2*log(N)->log(N)，你的内层循环是N^2/2->N^2。因此，时间复杂度为N^2*log(N)。

关于基准测试，当N=8或N=16时的值是荒谬的，循环中的时间与设置JVM、缓存失败等相比微不足道。你必须：

从最大的N开始，并检查它的评估情况。

对每个N值进行多次运行。

认为时间复杂度是衡量算法在N变得非常大时的工作效率的一种指标。

- SJuan76

---

内部循环为什么是N^2/2？我理解外部循环的值了。 - Max

好的，我太快了。我在考虑算术级数（当i = 2时有1次迭代，当i = 3时有2次迭代...），但没有想到i的取值为1、2、4、8、16等等。这是一个几何级数的值之和，我需要再次检查它。 - SJuan76

是的，我认为内部循环并不简单。 - Max

1 + 2 = 3 (2^2 -1), 1 + 2 + 4 = 7 (2^3 - 1)... 通常情况下，对于给定的i，迭代次数将为2^i - 1。 - SJuan76