java - 为什么这个 O(N^2) 算法运行得这么快？

Question

此算法的复杂度为 O(n²)，但运行时间不到一秒。为什么这么快？

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 );
    }

}

Answer 1

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

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

剩下的代码并不多，这就是它可能运行得如此之快的原因!

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

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

希望这对您有所帮助!