📚 课程目录第4章算法测试基础

4 算法测试基础：排序与查找算法测试、时间复杂度验证、边界用例设计

本章聚焦面试中高频的算法测试题：如何系统测试排序与查找算法、验证时间复杂度、穷举边界用例。掌握结构化回答框架，避免“只写代码不测边界”的常见失分点。

  本章学习目标：
  能独立设计排序/查找算法的全覆盖测试用例（含边界、重复、大数据）
掌握时间复杂度验证的反证法与基准测试思路
区分“功能正确”与“时间/空间符合预期”的测试维度

面试问题 如何测试一个快速排序算法的正确性和性能？

考察点：排序算法测试维度（功能、边界、性能）、时间复杂度验证方法、测试用例设计能力。

回答框架：功能测试 → 边界测试 → 性能测试 → 稳定性验证。

示例回答：我会分三步：1）功能测试：随机数组排序后验证有序；2）边界测试：空数组、单元素、已有序数组、全部相等数组；3）性能测试：用不同规模数据（10³~10⁶）统计耗时，拟合趋势确认O(n log n)。同时检查是否稳定排序（快速排序默认不稳定）。

可能追问：如果输入数组中包含大量重复元素，快速排序会退化吗？如何优化？

避坑提醒：不要只测随机数据。务必覆盖“已有序”“逆序”“全相同”等边界，否则面试官会认为你没有工程经验。

面试问题 二分查找算法的测试边界有哪些？如何验证其时间复杂度是O(log n)？

考察点：边界值分析（low/high、mid溢出）、循环不变式理解、时间复杂度实验验证。

回答框架：输入假设 → 边界列举 → 时间测量 → 反证法验证。

示例回答：边界包括：目标在首位、末位、奇数/偶数长度数组、目标不存在（小于最小、大于最大、中间缺失）。验证时间复杂度：在n=2¹⁰到2²⁰上分别运行，记录比较次数，绘制log₂n曲线，若斜率接近1说明O(log n)。

可能追问：mid = (left+right)//2 可能存在整数溢出问题，如何避免？

避坑提醒：不要只说“写单元测试”。要体现你理解“测试本身也需要理论验证”，比如用数学归纳法证明二分查找的正确性。

面试问题 请设计测试用例，验证一个“查找数组中第k大元素”算法（快速选择）的正确性和性能。

考察点：快速选择算法特性（与排序区别）、期望时间复杂度O(n)验证、随机化影响。

回答框架：功能测试 → 边界（k=1/k=n/k=中间值） → 重复元素 → 性能分布验证。

示例回答：功能：随机数组+已知第k大值做assert。边界：k=1（最小）、k=n（最大）；重复元素数组验证第k大是否返回正确值。性能：固定n=10⁵，运行100次取平均时间，验证线性趋势；同时检测最坏情况（已有序数组选首元素pivot）是否退化。

可能追问：如果要求算法必须是稳定的（即相等元素保持原始顺序），如何修改测试用例？

避坑提醒：不要假设pivot随机选取就万事大吉。一定要构造“有序数组”测试最坏情况，并说明可用三数取中或随机化避免。

项目名称	ROS导航系统中路径关键点排序模块测试
业务背景	机器人接收多个候选路径点，需按代价函数排序后选择最优路径。排序算法性能直接影响实时性（ms级响应）。
规模指标	候选点数量：10 ~ 10⁵；机器人主频2GHz；内存64MB；要求排序耗时<20ms。
技术栈	C++（std::sort）、ROS2、Google Test、valgrind（性能分析）。
核心难点	1）实时性要求下不能使用不稳定排序（路径点顺序影响后续约束）；2）输入数据存在大量重复代价（机器人路径点可能等距）。
面试高频追问	Q1：为什么选择std::sort而不是手写快排？ Q2：如何确保在内存受限环境下排序不产生额外分配？ Q3：重复代价数据如何测试排序稳定性？
可迁移回答话术	“我在项目中遇到类似场景，会先明确排序稳定性要求，然后构造包含相同代价的路径点测试，验证排序后相对顺序不变。性能测试采用不同规模数据集进行benchmark，同时监控内存峰值，确保实时性达标。”

项目复盘提示：面试官常让你描述“你在项目中遇到过什么算法测试难点”。重复排序稳定性、内存限制、性能基准是三个经典切入点，提前准备好对应话术。