倍率实验

ゝ一纸荒年。 2021-07-24 12:26 338阅读 0赞

# 一 代码 #

/******************************************************************************
 * Compilation: javac DoublingRatio.java
 * Execution: java DoublingRatio
 * Dependencies: ThreeSum.java Stopwatch.java StdRandom.java StdOut.java
 *
 *
 * % java DoublingRatio
 * 250 0.0 2.7
 * 500 0.0 4.8
 * 1000 0.1 6.9
 * 2000 0.6 7.7
 * 4000 4.5 8.0
 * 8000 35.7 8.0
 * 4000 3.9 6.6
 * ...
 *
 ******************************************************************************/
 
 package common;
 
 /**
 * The {@code DoublingRatio} class provides a client for measuring
 * the running time of a method using a doubling ratio test.
 * 
 * For additional documentation, see <a href="https://algs4.cs.princeton.edu/14analysis">Section 1.4</a>
 * of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */
 public class DoublingRatio {
 private static final int MAXIMUM_INTEGER = 1000000;
 
 // This class should not be instantiated.
 private DoublingRatio() {
 }
 
 /**
 * Returns the amount of time to call {@code ThreeSum.count()} with n
 * random 6-digit integers.
 *
 * @param n the number of integers
 * @return amount of time (in seconds) to call {@code ThreeSum.count()}
 * with n random 6-digit integers
 */
 public static double timeTrial(int n) {
 int[] a = new int[n];
 for (int i = 0; i < n; i++) {
 a[i] = StdRandom.uniform(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
 }
 Stopwatch timer = new Stopwatch();
 ThreeSum.count(a);
 return timer.elapsedTime();
 }
 
 /**
 * Prints table of running times to call {@code ThreeSum.count()}
 * for arrays of size 250, 500, 1000, 2000, and so forth, along
 * with ratios of running times between successive array sizes.
 *
 * @param args the command-line arguments
 */
 public static void main(String[] args) {
 double prev = timeTrial(125);
 for (int n = 250; true; n += n) {
 double time = timeTrial(n);
 StdOut.printf("%7d %7.1f %5.1f\n", n, time, time / prev);
 prev = time;
 }
 }
 }

# 二 测试 #

250     0.0   1.3
        500     0.1   7.3
       1000     0.1   1.2
       2000     0.5   7.2
       4000     3.6   6.9
       8000    23.5   6.6
      16000   185.2   7.9

# 三 说明 #

问题规模大1倍，时间变成原来的8倍。

倍率定理：如果T(N)~aN^blgN,那么T(2N)/T(N)~2^b,通过倍率定理，我们可以评估算法解决大型问题的可行性。