统计和为0的三元组的数量算法的性能分析

男娘i 2021-07-25 02:31 187阅读 0赞

**一 代码**

package common;
    
    public class ThreeSum {
        private ThreeSum() { }
        public static void printAll(int[] a) {
            int n = a.length;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    for (int k = j+1; k < n; k++) {
                        if (a[i] + a[j] + a[k] == 0) {
                            StdOut.println(a[i] + " " + a[j] + " " + a[k]);
                        }
                    }
                }
            }
        }
    
        public static int count(int[] a) {
            int n = a.length;
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    for (int k = j+1; k < n; k++) {
                        if (a[i] + a[j] + a[k] == 0) {
                            count++;
                        }
                    }
                }
            }
            return count;
        }
    
        public static void main(String[] args)  {
            In in = new In(args[0]);
            int[] a = in.readAllInts();
    
            Stopwatch timer = new Stopwatch();
            int count = count(a);
            StdOut.println("elapsed time = " + timer.elapsedTime());
            StdOut.println(count);
        }
    }

**二 测试**

F:\Algorithm\target\classes>java common.ThreeSum 1Kints.txt
    elapsed time = 0.202
    70
    
    F:\Algorithm\target\classes>java common.ThreeSum 2Kints.txt
    elapsed time = 1.673
    528
    
    F:\Algorithm\target\classes>java common.ThreeSum 4Kints.txt
    elapsed time = 12.656
    4039

**三 测试说明**

从测试结果来看，增长数量级是N的三次方。

**四 代码**

package MyDoublingTest;
    
    import common.StdOut;
    import common.StdRandom;
    import common.Stopwatch;
    import common.ThreeSum;
    
    /**
    * Copyright (C), 2020-2020, XXX有限公司
    * FileName: MyDoublingTest
    * Author:   cakin
    * Date:     2020/2/8
    * Description: 性能实验数据分析——统计和为0的三元组的数量
    */
    public class MyDoublingTest {
        private static final int MAXIMUM_INTEGER = 1000000;
    
        // This class should not be instantiated.
        private MyDoublingTest() { }
    
        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();
        }
    
        public static void main(String[] args) {
            for (int n = 250; true; n += n) {
                double time = timeTrial(n);
                StdOut.printf("%7d %7.1f\n", n, time);
            }
        }
    }

**五 测试结果**

250     0.0
        500     0.1
       1000     0.3
       2000     2.4
       4000    12.9
       8000   101.6