数据结构与算法 / 系统课时

算法正确性测试

算法正确性测试

实现能够编译、并在几个示例上得到正确结果,并不代表算法对全部输入都正确。本课建立示例测试、边界测试、随机差分测试和性质测试组成的验证链,并用固定随机种子得到可复现的 Java 测试结果。

学习目标

  • 能为算法设计正常输入、边界输入和退化输入。
  • 能使用参考实现进行随机差分测试,并复现失败样例。
  • 能用排序性、元素守恒等性质检查没有固定答案的大量输入。

四层测试策略

示例测试验证题目给出的典型路径,边界测试覆盖空输入、单元素、重复值和极端顺序。随机差分测试把待测实现与可信参考实现放在同一批输入上比较;性质测试则不依赖完整答案,而是检查结果必须满足的不变量。

算法正确性测试的四层防线

测试层次 主要目的 关键做法
示例测试 验证已知主路径 为典型输入写出精确期望值
边界测试 暴露下标和条件错误 覆盖空数组、单元素、重复值、已排序和逆序
随机差分测试 扩大输入覆盖面 使用固定种子生成输入,并与 Arrays.sort 比较
性质测试 检查结果不变量 同时验证非递减顺序与元素多重集合不变

排序算法只检查“结果有序”还不够,因为错误实现可能通过丢弃元素得到一个有序数组。因此至少同时验证:相邻元素非递减,以及排序前后每个值的出现次数完全一致。

完整可运行示例

将下面代码保存为 AlgorithmCorrectnessTest.java。示例测试一个插入排序实现,其中随机测试使用固定种子,因此任何失败都能在下一次运行中复现。

java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class AlgorithmCorrectnessTest {

    public static void main(String[] args) {
        runExampleTests();
        runBoundaryTests();
        runRandomDifferentialTests();
        runPropertyTests();
        System.out.println("全部测试通过");
    }

    private static void runExampleTests() {
        assertSortEquals(
                new int[]{5, 1, 4, 2, 8},
                new int[]{1, 2, 4, 5, 8}
        );
        assertSortEquals(
                new int[]{3, -1, 3, 0},
                new int[]{-1, 0, 3, 3}
        );
        assertSortEquals(
                new int[]{2, 1},
                new int[]{1, 2}
        );
        System.out.println("示例测试通过:3 组");
    }

    private static void runBoundaryTests() {
        assertSortEquals(new int[]{}, new int[]{});
        assertSortEquals(new int[]{7}, new int[]{7});
        assertSortEquals(new int[]{4, 4, 4}, new int[]{4, 4, 4});
        assertSortEquals(new int[]{1, 2, 3, 4}, new int[]{1, 2, 3, 4});
        assertSortEquals(new int[]{4, 3, 2, 1}, new int[]{1, 2, 3, 4});
        System.out.println("边界测试通过:5 组");
    }

    private static void runRandomDifferentialTests() {
        Random random = new Random(20260803L);

        for (int round = 0; round < 500; round++) {
            int[] actual = randomArray(random, 30);
            int[] expected = actual.clone();

            // 使用标准库排序作为本轮测试的参考实现。
            Arrays.sort(expected);
            insertionSort(actual);
            assertArrayEquals(expected, actual);
        }

        System.out.println("随机差分测试通过:500 组");
    }

    private static void runPropertyTests() {
        Random random = new Random(1803L);

        for (int round = 0; round < 500; round++) {
            int[] data = randomArray(random, 40);
            int[] original = data.clone();

            insertionSort(data);

            // 两个性质共同防止“有序但丢元素”的伪正确结果。
            assertNonDecreasing(data);
            assertSameMultiset(original, data);
        }

        System.out.println("性质测试通过:500 组");
    }

    private static int[] randomArray(Random random, int maxLength) {
        int length = random.nextInt(maxLength + 1);
        int[] data = new int[length];

        for (int i = 0; i < length; i++) {
            data[i] = random.nextInt(101) - 50;
        }

        return data;
    }

    private static void insertionSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int value = data[i];
            int j = i - 1;

            while (j >= 0 && data[j] > value) {
                data[j + 1] = data[j];
                j--;
            }

            data[j + 1] = value;
        }
    }

    private static void assertSortEquals(int[] input, int[] expected) {
        int[] actual = input.clone();
        insertionSort(actual);
        assertArrayEquals(expected, actual);
    }

    private static void assertArrayEquals(int[] expected, int[] actual) {
        if (!Arrays.equals(expected, actual)) {
            throw new AssertionError(
                    "期望 " + Arrays.toString(expected)
                            + ",实际 " + Arrays.toString(actual)
            );
        }
    }

    private static void assertNonDecreasing(int[] data) {
        for (int i = 1; i < data.length; i++) {
            if (data[i - 1] > data[i]) {
                throw new AssertionError("结果不是非递减序列");
            }
        }
    }

    private static void assertSameMultiset(int[] before, int[] after) {
        Map<Integer, Integer> counts = new HashMap<>();

        for (int value : before) {
            counts.merge(value, 1, Integer::sum);
        }

        for (int value : after) {
            counts.merge(value, -1, Integer::sum);
        }

        for (int count : counts.values()) {
            if (count != 0) {
                throw new AssertionError("排序前后的元素及其出现次数不一致");
            }
        }
    }
}

使用 JDK 17 或更高版本编译并运行:

bash
javac AlgorithmCorrectnessTest.java
java AlgorithmCorrectnessTest

预期输出

text
示例测试通过:3 组
边界测试通过:5 组
随机差分测试通过:500 组
性质测试通过:500 组
全部测试通过

常见错误与练习

常见错误

  • 只测试一个正常示例,会遗漏空数组、重复元素和逆序输入导致的边界错误。
  • 随机测试不固定种子,失败后无法生成同一输入,修复过程会变得不可重复。
  • 性质测试只检查顺序,不检查元素守恒,可能放过重复、丢失或新增元素的实现。
  • 直接把待测实现复制成参考实现,会让两边共享同一个缺陷;参考实现应来自独立算法或可信标准库。

本课练习

  1. 为二分查找编写示例、边界和随机差分测试。输入数组必须有序,并覆盖空数组、目标位于两端、目标不存在和重复值;验收条件是连续运行 1000 组固定种子随机数据均与线性查找结果一致。
  2. 人为把插入排序的循环条件改成 data[j] >= value,观察现有测试是否失败;再增加一个能够验证“稳定排序”的性质测试,验收条件是相同键值元素的原始相对顺序保持不变。

本课总结

  • 示例与边界测试负责已知风险,随机差分测试负责扩大输入空间。
  • 性质测试应验证多个独立不变量,避免只检查表面正确性。
  • 固定随机种子和完整失败输入是定位、修复与回归验证的基础。

下一课预告

下一课将学习“基准测试与性能剖析”,把已经验证正确的算法放入公平、可重复的测量环境,并用性能数据定位真正的优化目标。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

算法正确性测试

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通