0

这个算法是 O(n 2 )，但是它在不到一秒的时间内运行。为什么这么快？

public class ScalabilityTest {

   public static void main(String[] args) {
      long oldTime = System.currentTimeMillis();
      double[] array = new double[5000000];

      for ( int i = 0; i < array.length; i++ ) {
         for ( int j = 0; j < i; j++ ) {
            double x = array[j] + array[i];
         }
      }
      System.out.println( (System.currentTimeMillis()-oldTime) / 1000 );
   }
}

编辑：

我将代码修改为以下内容，现在运行速度非常慢。

public class ScalabilityTest {

public static void main(String[] args) {
    long oldTime = System.currentTimeMillis();
    double[] array = new double[100000];
    int p = 2;
    int m = 2;
    for ( int i = 0; i < array.length; i++ ) {
        p += p * 12348;
        for ( int j = 0; j < i; j++ ) {
            double x = array[j] + array[i];
            m += m * 12381923;
        }
    }

    System.out.println( (System.currentTimeMillis()-oldTime) / 1000 );
    System.out.println( p + ", " + m );
    }

}
4

4 回答 4

11

我认为这里的问题是一切都在优化。这是我的推理：

  1. x无需进行任何计算即可知道的值- 您的数组全为 0，因此x始终取值 0。
  2. 局部变量x未使用，可以优化掉。
  3. 内部循环什么都不做，所以可以优化掉。
  4. 外循环什么都不做，所以可以优化掉。

剩下的代码并不多，这就是为什么它可能运行得如此之快！

作为参考，我在自己的机器上进行了尝试，并通过不断将其乘以 10 来改变数组大小，并且发现性能完全没有变化 - 它总是完成并输出需要 0 秒。这与优化假设一致，即运行时间应为 O(1)。

编辑：您编辑的代码进一步支持了我的想法，因为现在循环体有副作用，因此无法优化。具体来说，由于m和p在循环内更新，编译器无法轻松地优化整个循环，因此您将开始看到 O(n 2 ) 性能。尝试改变数组的大小并观察会发生什么。

希望这可以帮助！

于 2013-06-13T19:19:13.330 回答
6

算法的顺序并不能告诉您它运行的速度。它告诉你当 n 的大小改变时它的速度如何演变。

O(n) = n^2 意味着如果您尝试使用 10,000,000 个元素，您将需要（大约）当前所需时间的 4 倍。

于 2013-06-13T19:19:31.037 回答
0

可能是 JIT 启动并优化了一些东西，因为双循环实际上并没有做任何事情。

请注意，这对于 Java 和 JVM 的每个版本和实现来说都太具体了——在我的版本上，它现在运行了大约一分钟。

您可以添加一个

System.out.println(x)

如果您想查看 O(N^2) 行为，则在 for 循环之后和之外只是为了停止优化。

于 2013-06-13T19:19:23.503 回答
0

我认为这无关紧要。O(N^2) 更快，但参考什么。你只能说某样东西快，只有当你把它和某样东西比较时。不是吗？

此外，时间也取决于输入大小。尝试大输入，您可以看到 O(N) 和 O(N^2) 之间的差异。

供一些实际参考。SPOJ是一个编程竞赛网站，它使用两个处理器来检查您的代码是否与输入文件相符。

  1. (Intel Pentium III 733 MHz) - 由自 2004 年开始为 SPOJ 服务的老式稳定的 Pentium III 机器组成。由于这些机器速度很慢，由 SPOJ 问题设置者创建的评委可以更轻松地测试算法的复杂性在您的解决方案中使用而无需创建大量数据集（您可以很容易地分辨出 O(n) 和 O(nlogn) 之间的区别）。

  2. (Intel Pentium G860 3GHz) - 这个新集群由现代且快速的 Intel Pentium G860 CPU 组成。在此，您的提交将比以前的提交快 30 到 50 倍。因此，您可以预期，如果您在家中测试您的解决方案，那么它将在 SPOJ 上具有相似的执行时间。在此集群上，提交的内存限制为 1536 MB。

更多：在 Intel Pentium G3860 3GHZ 上，通常在 1 秒内循环最多 10^7 次运行。所以你的 10^7 的 O(N) 算法只需要 1 秒。现在拿 N=10^7 做 O(N^2) 试试看..你可以自己体验时差

编译器优化在这方面也起着重要作用！你的代码也太简单了！你的数组是空的！

于 2013-06-13T20:42:43.667 回答