查看“︁算法与复杂度”︁的源代码

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

== 在五个数中找最大值 ==
输入为非空的有限数列 <math>a_1,ldots,a_n</math>，数值之间能够比较大小；输出其中的最大值。先把第一个数记作当前最大值 <math>m</math>，随后从左到右读入余下各项。每读到一个数，只在它大于 <math>m</math> 时更新 <math>m</math>。

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

[[File:Gezhi-algorithm-max-prefix.svg|frame|center|alt=从左到右读取十二、五、十七、九、十四，五步保存的最大值依次为十二、十二、十七、十七、十七；前三项的最大值为十七|每一步的 m 都是目前读过的数中最大的一个；第三步读到 17 时才改变。]]

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

== 为什么最后的数一定正确 ==
逐步计算时保持一个'''循环不变式'''：读完前 <math>j</math> 项后，<math>m=max{a_1,ldots,a_j}</math>。

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

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

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

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

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

[[File:Gezhi-algorithm-comparison-growth.svg|frame|center|alt=横轴输入长度四、八、十六；逐项扫描的比较次数为三、七、十五，逐对比较为六、二十八、一百二十|相同任务和计费规则下，逐项扫描随输入长度线性增长；逐对比较增长更快。]]

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

== O、Ω 与 Θ 各说什么 ==
令 <math>g(n)</math> 是非负的成本函数，<math>f(n)</math> 在足够大的 <math>n</math> 上为正。写 <math>g(n)=O(f(n))</math>，是说存在常数 <math>C>0,n_0</math>，对所有 <math>nge n_0</math> 都有 <math>g(n)le C f(n)</math>；写 <math>g(n)=\Omega(f(n))</math>，则是不等号反向的下界。两者同时成立，记为 <math>g(n)=\Theta(f(n))</math>，即上下界只差固定倍数。

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

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

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

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

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

== 参考资料与继续阅读 ==
* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-1-algorithms-and-computation/ MIT 6.006，Lecture 1：Algorithms and Computation]：算法的正确性与效率为何要分别说明。
* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/c6d8f06c6f11e3342633dec85498f551_MIT6_006S20_r01.pdf MIT 6.006，Recitation 1：Asymptotic Notation]：O、Ω、Θ 的常数定义。
* [https://algs4.cs.princeton.edu/14analysis/ Sedgewick、Wayne，Analysis of Algorithms]：先说明基本操作，再讨论增长与实际测时。
* 先修：[[逻辑]]、[[函数]]；后续：[[二分法]]、[[牛顿法]]、[[最短路径]]、[[单纯形法]]。
[[分类:算法]]