0

このアルゴリズムは O(n 2 ) ですが、実行時間は 1 秒未満です。なぜそんなに速いのですか？

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) であるべきであるという最適化仮説と一致しています。

EDIT :編集されたコードは、ループの本体に副作用があり、最適化できないため、私の考えをさらにサポートします。具体的には、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 の各バージョンと実装に固有すぎることに注意してください。私のバージョンでは、現在約 1 分間実行されています。

あなたは追加するかもしれません

System.out.println(x)

O（N ^ 2）の動作を確認したい場合は、forループの後と外側で最適化を停止します。

于 2013-06-13T19:19:23.503 に答える