算法与复杂度

算法（algorithm）是为一类输入规定的有限计算步骤。评价一个算法，先问它在约定输入上是否停止、返回的答案是否正确，再问完成计算需要多少资源。复杂度讨论资源用量怎样随输入规模变化；它不能代替正确性证明。

在五个数中找最大值

输入为非空的有限数列 $a_{1}, \dots, a_{n}$ ，数值之间能够比较大小；输出其中的最大值。先把第一个数记作当前最大值 $m$ ，随后从左到右读入余下各项。每读到一个数，只在它大于 $m$ 时更新 $m$ 。

对 $(12, 5, 17, 9, 14)$ ，初始 $m = 12$ ；读到 5 不变，读到 17 更新，后两项都不改变结果。图把已读前缀和每一步保存的数对齐，最下方的等式只说前三项已经处理完时的状态。

从左到右读取十二、五、十七、九、十四，五步保存的最大值依次为十二、十二、十七、十七、十七；前三项的最大值为十七 — 每一步的 m 都是目前读过的数中最大的一个；第三步读到 17 时才改变。

若输入只有一个数，就直接返回它；空数列没有最大值，本算法要求输入非空。若还需返回最大值的位置，相等时是否更新位置也要事先约定。以下只返回数值。

正确性与终止性

逐步计算时保持一个循环不变式：读完前 $j$ 项后， $m = max (a_{1}, \dots, a_{j})$ 。

开始时只读了第一项， $m = a_{1}$ ，不变式成立。假设读完前 $j$ 项时成立。下一项若比 $m$ 大，更新后的它就是前 $j + 1$ 项最大值；否则原来的 $m$ 仍是最大值。不变式因此从一步传到下一步。下标每次增加一，有限次后必到 $j = n$ ；此时不变式正好给出所求答案。

这份证明分开处理了正确性与终止性：不变式保证结束时答对，有限上界与递增下标保证确实会结束。试算几个输入只能帮助发现错误，不能代替对任意允许输入的论证。

把初值偷偷设为零会破坏起始步骤。例如输入 $(- 12, - 5, - 17, - 9, - 14)$ 时，零不在数列中，算法会错误地返回零。按第一项初始化，第二步改为 $- 5$ ，以后不再更新，正确答案为 $- 5$ 。这个变式也检验了证明里“最大值必须来自已读输入”的前提。

数量级从哪一次操作数起

取大小比较为基本操作，并暂且把一次比较看作固定成本。对长度 $n$ 的输入，第一项用于初始化，其余每项恰比较一次，所以比较次数严格等于 $T (n) = n - 1$ ，与数字排列顺序无关。除输入本身外，只保存当前最大值与位置计数，额外空间为常数量级。若原数列本来存于内存，其占用的 $n$ 个位置当然不能算作“额外空间”。

另一种办法是把每一对元素都比较一遍，再找出未被更大元素击败的值。它也能找到最大值，却固定做 $n (n - 1) / 2$ 次比较。长度为 4、8、16 时，逐项扫描分别比较 3、7、15 次，逐对比较则为 6、28、120 次。下面的图按同一比较计费规则画出这些准确次数；连线帮助看增长趋势，不代表实际运行秒数。

横轴输入长度四、八、十六；逐项扫描的比较次数为三、七、十五，逐对比较为六、二十八、一百二十 — 相同任务和计费规则下，逐项扫描随输入长度线性增长；逐对比较增长更快。

对只通过两两比较来判断大小、且数值各不相同的任意正确算法，最坏情况下至少需要 $n - 1$ 次比较。理由是：除最大值以外，每个数必须至少在一次比较中输给别的数，否则它仍可能是最大值；一次比较至多使一个候选输掉。因此逐项扫描在这个比较模型下已经达到比较次数下界。换了任务或允许额外信息，这个下界不能原封不动套用。

渐近上界、下界与紧界

令 $g (n)$ 是非负的成本函数， $f (n)$ 在足够大的 $n$ 上为正。写 $g (n) = O (f (n))$ ，是说存在常数 $C > 0, n_{0}$ ，对所有 $n \geq n_{0}$ 都有 $g (n) \leq C f (n)$ ；写 $g (n) = Ω (f (n))$ ，则是不等号反向的下界。两者同时成立，记为 $g (n) = Θ (f (n))$ ，即上下界只差固定倍数。

例如对 $n \geq 2$ ，有 $n / 2 \leq n - 1 \leq n$ ，故逐项扫描的比较次数是 $Θ (n)$ 。说它是 $O (n^{2})$ 也没有逻辑错误，却放宽了已知界，无法显示它与逐对比较的差别。逐对比较的 $n (n - 1) / 2$ 则为 $Θ (n^{2})$ 。

这里的上界和下界描述的是已经指定的算法成本函数。上一节“任何比较算法至少 $n - 1$ 次”的论证更强：它是同一问题在该计算模型中的下界。两种下界的对象不同，不能混为一谈。

数量级不等于实际用时

上面的线性结论依赖计费规则。若数是任意精度整数，两个很长的数比较大小所用步骤可能随位数增加；此时只写元素个数 $n$ ，没有充分描述输入大小。缓存、内存布局和实现语言也会影响实际秒数。复杂度提供可迁移的增长比较，性能测试则回答具体机器上的用时，两者可以互相核对。

某些算法的操作次数随输入排列变化，要说明报告的是最坏情况、平均情况还是其他口径；平均情况需要指定输入的概率模型。若算法自己使用随机选择，还要说明期望是对随机选择取的，还是也对输入分布取的。不能把一次运行较快当成对所有输入的复杂度保证。

读其他算法时，可以沿相同顺序追问：输入、输出及不允许的情形是什么；哪一项状态始终保持；为何能停止；基本操作如何计费；答案和误差由什么条件保证。二分法保存异号根区间，牛顿法利用切线但需要局部条件，最短路径依据边权选用不同更新规则。它们的正确性理由与成本模型都不同。

参考资料与继续阅读

MIT 6.006，Lecture 1：Algorithms and Computation：算法的正确性与效率为何要分别说明。
MIT 6.006，Recitation 1：Asymptotic Notation：O、Ω、Θ 的常数定义。
Sedgewick、Wayne，Analysis of Algorithms：先说明基本操作，再讨论增长与实际测时。
先修：逻辑、函数；后续：二分法、牛顿法、最短路径、单纯形法。