4

我正在学习 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 的 2 次幂，这怎么可能？

到目前为止我做了什么：

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

4

4 回答 4

3

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

2 到 N * N 的幂的总和约为 2 * N * N 或 O(N ^ 2)

注意：当 N=100000 时，N*N 将溢出，因此其结果具有误导性。如果您认为溢出是问题的一部分，那么对于大数来说，总和是相当随机的，因此您可以争论它的 O(1)，即如果 N=2^15，N^2 = 2^30，总和将为整数.MAX_VALUE。没有更高的 N 值会给出更高的总和。

于 2012-08-12T19:50:41.083 回答
3

这里有很多混淆，但重要的是Big-O 符号是关于增长率的，或者数学家会说的限制行为。函数将在 O(n*n) 中执行意味着执行时间将比例如n增加得更快，但比例如2^n慢。

使用大 O 表示法进行推理时，请记住常量“不算数”。这个特定问题有一些怪癖。

  • 如果循环是常规的N*Nfor 循环，则表达式 it-self 将导致 O(log n*n) 复杂度...
  • ...但是，for循环增量导致外部循环大约执行 log n 并且如果内部循环的内容在独立于ni = i*2的时间内运行，则函数将在 O(log n) 中。
  • 但同样，内循环运行时间取决于n，但它不执行 n*n 运行，而是大致记录 (n*n)/2 个循环。记住“常数不算数”并且我们最终会得到 O(n*n)。

希望这可以解决问题。

于 2012-08-12T19:52:19.400 回答
2

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

于 2012-08-12T20:13:34.277 回答
0

你的外循环是 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 变得非常大时算法如何工作的度量。

于 2012-08-12T19:51:37.950 回答