跨卷导读：算法、正确性与复杂度

从“步骤能跑”到“结论可证明”

第4卷第2章《积跬步，致千里》从泰朵拉带来的算法卡片开始：计算机不会凭直觉补全步骤，只会依照明确、无歧义且有限的指令执行。卡片上的例子是数列 A={31,41,59,26,53} 与目标 v=26；从第一个元素开始检查，就是最朴素的顺序查找。

先预测：一个程序在一百万个随机样例上都得到正确答案，是否已经证明算法正确？没有。测试只观察有限输入；证明要覆盖问题规格允许的全部输入。本章把算法当作一件完整交付物：先规定问题，再构造步骤，继而证明正确和终止，最后量化时间、空间与概率保证。

一、问题规格先于代码

把“找到目标”改写成契约。给定数列 A、目标 v，若要求返回第一次出现的位置 r，后置条件应包含：

以及

还要写清 n 是非负整数、数组下标有效、比较操作的语义，以及数据是否已经排序。若忽略“第一次”，返回任意一个重复位置也许仍是另一个合法问题的答案；规格不完整，代码就无从验收。

mg4-02 的最小计算模型

官方锚点把伪代码拆成赋值、条件、循环、返回和控制流，并暂时假设每行基本操作耗时相同。对顺序查找，令 M 为命中下标；若命中，逐行计数得到 4M+2，示例中 M=4 时是 18 步。若找不到，所有 n 个元素都要比较，循环条件还要被观察到，计数可写为 4n+5。

这个数字不是机器秒表，而是模型内的精确计数。模型改变，例如把大整数乘法当作常数时间，结论的含义也会改变。算法分析首先回答“在什么模型里数什么”，然后才比较快慢。

把算法卡片读成可复核的证据

算法的基本性质可以逐项验收：它接收明确的输入，产生约定的输出，步骤具有确定性和可行性，还要满足有穷性，也就是指令明确且无歧义，并在有限步后停止。伪代码中的 procedure、if/else、while 先检查条件，return 立即结束流程；这些不是排版习惯，而是把算法交给计算机却只能依照给定步骤执行的最小语法。

顺序查找把这些性质落到一组具体数据：A={31,41,59,26,53}、v=26，从第一个元素开始检查，目标可能能找到，也可能无法找到。目标是首次出现位置时，M 不是任意一个出现位置；它必须是最小的合法下标。这里先固定输入数列大小n，再把每一个分支翻译成可计数的基本操作。

在逐行调试时，程序位置、变量与分支组成一张可复现的状态表；示例中命中位置对应第18步。行级模型把每行伪代码的运行时间相同作为假设，运行时间是各行运行次数之和，因此命中位置为 M 时得到 4M+2；代入 M=4，就是4乘4加2等于18。用具体例子回代，是检查公式是否忠于控制流的低成本方法。

找不到 v 时，所有n个元素都要比较，循环条件还要检查第 n+1 次，所以可记为 k=n+1，也就是循环条件运行n+1次；普通版本的最坏计数是 4n+5。循环终止必须被观察到，否则把最后一次条件判断漏掉，算法分析会低估实际步骤。

为了把命中和失败归纳为一种情况，可以引入成功指示器S：找到时S=1，找不到时S=0，而 1-S指示失败。找不到时约定 M=n，统一公式会出现 M+1-S、M-S 等边界修正；最后得到 4M-3S+5，再代回两种取值，就能同时复核命中与未命中。这里每个变量都要保留变量的意义，不能为了凑公式而换掉语义。

哨兵优化把目标主动放进 A[n+1]，这个额外位置就是哨兵，它保证搜索不会越过该位置，让循环内部只比较元素；退出后再用一次 k小于等于n 判断命中是否来自原数组。完整的带有哨兵的顺序查找算法可得 3M-3S+7，官方测试用例16步，比普通版18步少2步；差值为 M-2，所以 M大于2时哨兵版更快。

优化也会增加前提：数组必须有可写的n+1位置，并且要保存并恢复原值。在这个明确前提下，普通版最坏4n+5、哨兵版最坏3n+7，主项从 4M 降为 3M，约减少 25%。这就是明确前提条件的定量评估：精确计数帮助未来的人验证和使用，而渐近分析再把两种顺序查找都归为 O(n)，因为精确计数与渐近分析回答不同问题。第4卷还提到高德纳在20世纪60年代推动了“算法分析”这一名字；历史背景不替代证明，却提醒我们记录模型是长期协作的一部分。

二、用不变量证明搜索正确

考虑不使用哨兵的首个命中搜索：

function firstIndex(values: readonly number[], target: number): number {
  let index = 0;
  while (index < values.length && values[index] !== target) {
    index += 1;
  }
  return index < values.length ? index : -1;
}

终止性 取为：每次检查循环条件前，区间 [0,index) 中没有元素等于 target。

1. 初始化：index=0，区间为空，命题成立。
2. 保持：进入循环说明当前元素不等于目标；递增后，新扩大的区间仍然没有目标。
3. 退出：若因命中退出，结合不变量可知这是第一次出现；若因 index=n 退出，所有元素都已排除，返回 -1。

这三步证明的是部分正确性：如果循环结束，返回值满足契约。还要证明终止。令排名函数为 V=n-index；进入循环时 V 是非负整数，每次迭代严格减 1，不可能无限下降，所以循环必然结束。

哨兵版本把目标临时写到 A[n+1]，令循环内部只比较元素，可能把最坏计数从 4n+5 降到 3n+7。但它的前置条件增加了可写空间，且必须保存并恢复原值，特别要处理空数组、目标原本位于末位和异常退出。少两次比较不等于少掉证明义务。

三、从精确计数到渐近复杂度

必须带着计算模型和量化对象谈。顺序查找的最坏精确计数是 4n+5；哨兵版是 3n+7。当 n 变大，常数项和低阶项不决定增长阶，因此两者都是 O(n)，但精确计数仍能说明同一阶内的常数改进。

若输入有序，可以用二分搜索：维护目标若存在必在 [lo,hi] 中的区间不变量，每次比较中点后把候选区间缩小一半。最多进行 ⌈log₂(n+1)⌉ 次比较；排序是它的前置条件，不能把无序数组直接套上 O(log n) 的结论。

最坏、输入平均和随机期望也要分开。对确定性算法 A 与规模为 n 的输入集合 I_n：

若另外规定输入分布 D_n，才有 T_{\mathrm{avg}}(n)=\mathbb E_{x\sim D_n}[T_A(x)]。若算法对固定输入 x 自己掷随机位串 r，则随机期望是 T_{\mathrm{rand}}(x)=\mathbb E_r[T_A(x;r)]。三者的随机性来源与保证对象不同。

四、选择策略必须携带证明义务

穷举是可靠基线：候选集合完整、验证器正确，就不会漏解；但 n 个布尔变量有 2^n 个赋值，指数增长很快变得不可承受。分治要求子问题规模变小且答案可组合；若子问题大量重叠，缓存可能更合适，这不是分治定义的一部分。

贪心选择必须证明“现在选了以后不会后悔”。面额 [1,3,4] 找 6 时，最大面额优先得到 4+1+1 三枚，而最优是 3+3 两枚；这个反例足以否定该币制上的无条件贪心。Dijkstra 的贪心固定最小暂定距离，则依赖所有边权非负；有负边时不能沿用同一个证明。

动态规划也不只是“递归加缓存”。0-1 背包可以定义 dp[i][w] 为前 i 件物品、容量不超过 w 的最大价值，再按是否选择第 i 件物品分成互斥且完备的两个分支。状态必须保留未来转移所需的信息，边界、依赖顺序和最优子结构都要说明。

排序的比较模型还给出一个边界：n 个互异元素有 n! 种排列，二元比较树的叶子至少有 n! 个，因此高度 h 满足

这只约束基于比较的通用排序；计数排序使用键值范围，不能把两个模型混为一谈。

五、随机性改变的是保证对象

随机快速排序固定输入数列，内部均匀选择枢纽。若枢纽恰好落在端点，递归树退化，最坏时间是 Θ(n²)；但对每个固定输入，把所有枢纽选择取期望，比较次数的期望为 Θ(n log n)。这是期望保证，不是宣称每次运行都达到相同步数。

随机 3-SAT 的随机步骤也不能被写成“随机就能消除困难”：必须先定义成功事件，再给出单次成功概率，最后用独立重复说明失败概率如何下降。平均随机输入与固定输入上的随机算法看起来有相同的期望符号，却回答不同问题。

交互实验：让证据跟着输入走

先选择目标，再分别观察顺序查找和二分搜索访问了哪些位置。切换算法只改变步骤数，不改变契约；选择一个不在数组中的目标，则要观察两者如何证明“没有找到”。“重置”会恢复官方示例的输入和目标，方便复现实验。

分步验收：四份证据拼成一个算法

本章回顾：算法交付的五个问题

• 规格是什么？ 输入、输出、前置条件、后置条件和边界是否明确。
• 为什么正确？ 不变量证明部分正确性，排名函数证明终止性。
• 代价如何增长？ 先声明基本操作和输入规模，再区分精确计数、最坏、平均和随机期望。
• 条件在哪里？ 二分搜索需要有序输入，Dijkstra 需要非负边权，比较排序下界只在比较模型成立。
• 证据能复现吗？ 实验显示运行轨迹，练习要求回写契约；测试寻找反例，不能替代全称证明。

练习与答案