算法 - 算法分析

数学模型

1. 近似

例如下文 ThreeSumSlow 的内循环执行 N³/6-N²/2+N/3 次，N 很大时后两项可以忽略，记为 ~N³/6。~f(N) 表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。

2. 增长数量级

N³/6-N²/2+N/3 的增长数量级为 O(N³)。增长数量级将算法与它的具体实现隔离开来，一个算法的增长数量级为 O(N³) 与它是否用 Java 实现，是否运行于特定计算机上无关。

3. 内循环

执行最频繁的指令决定了程序执行的总时间，把这些指令称为程序的内循环。例如 ThreeSumSlow 的内循环是最内层的 if 语句，执行约 N³/6 次；外面两层循环中的语句最多执行约 N²/2 次，对总时间的影响可以忽略。

4. 成本模型

成本模型规定统计哪一种基本操作的次数来评估算法，例如 ThreeSum 统计数组的访问次数，排序算法统计比较和交换的次数。

注意事项

1. 大常数

在求近似时，如果低级项的常数系数很大，那么近似的结果是错误的。例如 N² + 1000N 近似为 ~N²，但 N = 1000 时低次项和高次项一样大。

2. 缓存

计算机系统会使用缓存技术来组织内存，访问数组相邻的元素会比访问不相邻的元素快很多。

3. 对最坏情况下的性能的保证

在核反应堆、心脏起搏器或者刹车控制器中的软件，最坏情况下的性能是十分重要的。例如快速排序平均只需要 ~2NlnN 次比较，最坏却需要 ~N²/2 次，需要最坏情况保证时可以改用归并排序或堆排序。

4. 随机化算法

通过打乱输入，去除算法对输入的依赖。例如快速排序先随机打乱数组，避免有序输入导致的最坏情况。

5. 均摊分析

将所有操作的总成本除以操作总数来将成本均摊。例如对一个空栈（数组实现，满时容量翻倍）进行 N 次连续的 push() 调用需要访问数组的次数为 N+4+8+16+...+2N=5N-4（N 为 2 的幂）：N 是向数组写入元素的次数；容量从 k 扩大到 2k 时，新数组初始化 2k 个元素，复制旧元素读、写各 k 次，共 4k 次，k 依次为 1、2、4……N/2。例如 N = 8 时共 8 + 4 + 8 + 16 = 36 次，均摊后访问数组的平均次数为常数。

ThreeSum

ThreeSum 用于统计一个数组中和为 0 的三元组数量。为了突出算法本身，下面的代码假设元素的绝对值较小（倍率实验中都在 ±10⁶ 之内），求和、取相反数都不会超出 int 的范围；否则要先转为 long 再计算。

public interface ThreeSum {
    int count(int[] nums);
}

1. ThreeSumSlow

该算法的内循环为 if (nums[i] + nums[j] + nums[k] == 0) 语句，总共执行的次数为 N(N-1)(N-2)/6 = N³/6-N²/2+N/3，因此它的近似执行次数为 ~N³/6，增长数量级为 O(N³)。

public class ThreeSumSlow implements ThreeSum {
    @Override
    public int count(int[] nums) {
        int N = nums.length;
        int cnt = 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 (nums[i] + nums[j] + nums[k] == 0) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

2. ThreeSumBinarySearch

将数组进行排序，对两个元素求和，并用二分查找方法查找是否存在该和的相反数，如果存在，就说明存在和为 0 的三元组。

应该注意的是，只有数组不含有相同元素才能使用这种解法，否则二分查找的结果会出错。

该方法可以将 ThreeSum 算法增长数量级降低为 O(N²logN)。

import java.util.Arrays;

public class ThreeSumBinarySearch implements ThreeSum {

    @Override
    public int count(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int target = -nums[i] - nums[j];
                int index = BinarySearch.search(nums, target);
                // 应该注意这里的下标必须大于 j，否则会重复统计。
                if (index > j) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

public class BinarySearch {

    public static int search(int[] nums, int target) {
        int l = 0, h = nums.length - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (target == nums[m]) {
                return m;
            } else if (target > nums[m]) {
                l = m + 1;
            } else {
                h = m - 1;
            }
        }
        return -1;
    }
}

3. ThreeSumTwoPointer

更有效的方法是先将数组排序，然后使用双指针进行查找，时间复杂度为 O(N²)。

固定 nums[i] 后，在它右侧的有序区间中用 l、h 两个指针从两端向中间找和为 -nums[i] 的两个数。和太小时 l 右移：nums[l] 与 h 左侧任何元素的和只会更小，nums[l] 不可能再组成答案；和太大时同理 h 左移。每次移动都排除一个元素，所以每个 i 只需 O(N) 次比较。

同样不适用于数组存在重复元素的情况。

import java.util.Arrays;

public class ThreeSumTwoPointer implements ThreeSum {

    @Override
    public int count(int[] nums) {
        int N = nums.length;
        int cnt = 0;
        Arrays.sort(nums);
        for (int i = 0; i < N - 2; i++) {
            int l = i + 1, h = N - 1, target = -nums[i];
            while (l < h) {
                int sum = nums[l] + nums[h];
                if (sum == target) {
                    cnt++;
                    l++;
                    h--;
                } else if (sum < target) {
                    l++;
                } else {
                    h--;
                }
            }
        }
        return cnt;
    }
}

倍率实验

如果 T(N) ~ aN^blogN，那么 T(2N)/T(N) ~ 2^b。

例如对于暴力的 ThreeSum 算法，近似时间为 ~N³/6。进行如下实验：多次运行该算法，每次取的 N 值为前一次的两倍，数组元素为 [-10⁶, 10⁶] 内的随机整数，统计每次执行的时间，并统计本次运行时间与前一次运行时间的比值，得到如下结果（JDK 21 实测，见附录 A1）：

N 较小时运行时间只有几毫秒，计时误差和 JIT 编译的影响较大，比值偏离 8；N 增大后比值稳定在 8 附近，即 T(2N)/T(N) ~ 2³，因此可以确定 T(N) ~ aN³。

import java.util.Random;

public class RatioTest {

    public static void main(String[] args) {
        Random random = new Random(42);
        int N = 250;
        int loopTimes = 6;
        double preTime = -1;
        while (loopTimes-- > 0) {
            int[] nums = new int[N];
            for (int i = 0; i < N; i++) {
                nums[i] = random.nextInt(2_000_001) - 1_000_000; // [-10^6, 10^6]
            }
            StopWatch.start();
            ThreeSum threeSum = new ThreeSumSlow();
            int cnt = threeSum.count(nums);
            double elapsedTime = StopWatch.elapsedTime();
            double ratio = preTime == -1 ? 0 : elapsedTime / preTime;
            System.out.println(N + "  " + cnt + "  " + elapsedTime + "  " + ratio);
            preTime = elapsedTime;
            N *= 2;
        }
    }
}

public class StopWatch {

    private static long start;


    public static void start() {
        start = System.currentTimeMillis();
    }


    public static double elapsedTime() {
        long now = System.currentTimeMillis();
        return now - start;
    }
}

附录：实测

A1. ThreeSumSlow 的倍率实验

环境：Temurin JDK 21.0.13，Apple M1 Pro。代码为正文中的 ThreeSum、ThreeSumSlow、StopWatch 和 RatioTest，直接运行 java RatioTest。每行依次为 N、和为 0 的三元组数量、耗时（ms）、与上一行的耗时比值：

250  1  6.0  0.0
500  5  20.0  3.3333333333333335
1000  60  149.0  7.45
2000  494  1195.0  8.020134228187919
4000  4035  10301.0  8.620083682008369
8000  32176  83576.0  8.11338704980099

参考资料

• Sedgewick R, Wayne K. 算法（第 4 版）[M]. 人民邮电出版社, 2012.
• Algorithms, 4th Edition