为什么这个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 ²)性能.尝试改变阵列的大小,看看会发生什么.

希望这可以帮助!

Answer 2

算法的顺序不会告诉您它运行的速度.它告诉你当n的大小发生变化时它的速度如何变化.

由于O(n)= n ^ 2意味着如果您尝试使用10,000,000个元素,则需要(大约)当前所需时间的4倍.