为什么这个O（N ^ 2）算法的运行如此之快？ [英] Why does this O(N^2) algorithm run so quickly?

问题描述

这个算法为O（n ² ），但它运行在不到一秒钟。为什么这么快？

 公共类ScalabilityTest {

   公共静态无效的主要（字串[] args）{
      长古来= System.currentTimeMillis的（）;
      双[]数组=新的双[5000000]

      的for（int i = 0; I＆LT; array.length;我++）{
         对于（INT J = 0; J＆LT;我; J ++）{
            双X =阵列[J] +阵列[I]
         }
      }
      的System.out.println（（System.currentTimeMillis的（） - 古来）/ 1000）;
   }
}
 

编辑：

我修改了code以下，现在它的运行速度非常慢。

 公共类ScalabilityTest {

公共静态无效的主要（字串[] args）{
    长古来= System.currentTimeMillis的（）;
    双[]数组=新的双[100000]。
    INT P = 2;
    INT米= 2;
    的for（int i = 0; I＆LT; array.length;我++）{
        P + = P * 12348;
        对于（INT J = 0; J＆LT;我; J ++）{
            双X =阵列[J] +阵列[I]
            M + = M * 12381923;
        }
    }

    的System.out.println（（System.currentTimeMillis的（） - 古来）/ 1000）;
    的System.out.println（P +，+米）;
    }

}
 

解决方案

我觉得这里的问题是，一切都得到优化掉。这里是我的推理：

1. 的 X 可以知道无需做任何计算的价值 - 你的阵列全为0，因此 X 将始终以0值。
2. 局部变量 X 不使用，可以优化掉。
3. 在内环什么也不做，所以可以被优化掉。
4. 在外环不做任何事，所以可以被优化掉。

你有没有那么多code，这就是为什么它可能这么快运行留下！

有关的参考，我想这对我自己的机器，并不断通过其10倍乘以不同的数组大小，看到绝对性能上没有变化 - 它总是完成并输出认为，需要0秒。这是与优化设定，其中列明了运行时应该为O一致（1）。

修改：您编辑code进一步支持我的想法，因为环路现在的身体有副作用，因此不能被优化掉。具体而言，由于 M 和 P 是循环内更新，编译器无法轻松优化环路之外的全部，所以你会开始看到为O（n ² ）的性能。尝试改变数组的大小，看会发生什么。

希望这有助于！

This algorithm is O(n²), however it runs in less than a second. Why is it so quick?

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

EDIT:

I modified the code to the following and now it runs very slowly.

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

}

解决方案

I think the issue here is that everything is getting optimized away. Here's my reasoning:

1. The value of x can be known without having to do any computation - your array is all 0s, so x will always take the value 0.
2. The local variable x is unused and can be optimized away.
3. The inner loop does nothing, so can be optimized away.
4. The outer loop does nothing, so can be optimized away.

You're left with not all that much code, which is why it probably runs so quickly!

For reference, I tried this on my own machine and varied the array size by constantly multiplying it by a factor of 10 and saw absolutely no change in performance - it always finished and outputted that 0 seconds were required. This is consistent with the optimization hypothesis, which states the runtime should be O(1).

EDIT: Your edited code further supports my idea since now the body of the loop has side-effects and therefore cannot be optimized away. Specifically, since m and p are updated inside the loop, the compiler cannot easily optimize the loop away in its entirety, so you would begin to see O(n²) performance. Try varying the size of the array and watch what happens.

Hope this helps!

这篇关于为什么这个O（N ^ 2）算法的运行如此之快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！