第 01 章 算法与算法分析入门：插入排序、归并排序与循环不变式

本章合并原书第 1 章（算法在计算中的作用）与第 2 章（入门）。第 1 章回答"为什么要研究算法"，第 2 章用两个排序算法把全书的工作方式一次演示完：怎样描述算法、怎样证明它正确（循环不变式）、怎样分析它花多少时间（RAM 模型、最坏情况、增长量级），以及怎样用分治法设计出更快的算法。后面所有章节都沿用这套框架，所以这一章值得慢读。

学习目标

1. 说清算法、计算问题、问题实例、正确性这几个概念，知道"候选解极多"与"NP 完全"意味着什么。
2. 用"初始化—保持—终止"三步写出循环不变式证明，并能为插入排序、MERGE、线性查找写出不变式。
3. 在 RAM 模型下逐行统计代价，得到插入排序最好、最坏情况的精确表达式，并抽象为 \(\Theta(n)\)、\(\Theta(n^2)\)。
4. 理解分治法的三步结构，写出归并排序的递归式，并用递归树得到 \(\Theta(n\lg n)\)。
5. 能估算常数因子与增长率谁更重要，找到两个算法的交叉点。
6. 能把排序、归并、逆序对计数用到量化场景中，例如用归并排序在 \(O(n\lg n)\) 时间内算 Kendall \(\tau\)。

读前导读

这一章在解决什么问题

整本第 09 册都在回答一个问题：同样一件事，让计算机怎么做才又对又快。这一章先把三个最基本的词讲清楚。

算法就是一份写死了每一步的操作手册。你熟悉的例子其实很多：用直线法算折旧、按 FIFO 结转存货成本、用二叉树一步步往回折现给期权定价，都是"给定输入、按固定步骤、得到输出"的过程。只要步骤足够明确、机器能照着执行，它就是算法。

复杂度回答"数据变多时，耗时怎么变"。本章最重要的直觉是：别看秒数，看"数据量翻倍时，耗时翻几倍"。插入排序在最坏情况下，数据翻倍耗时约变成 4 倍（这就是 \(n^2\) 量级）；归并排序数据翻倍耗时只比 2 倍多一点（这就是 \(n\lg n\) 量级）。股票池从 500 只扩到 5000 只，前者慢 100 倍，后者慢约 13 倍。这和你在 CFA 里比较"单利与复利"的思路一样：短期差别不大，规模一拉长，增长方式决定一切。

递归是"自己调用自己"：要排好一堆数，先把它劈成两半，各自排好（用的还是同一个方法），再合并。这像合并报表：集团报表 = 各子公司报表合并，子公司报表又 = 各孙公司报表合并，一直拆到单体公司为止。本章的归并排序就是这么设计的。

最后，本章用循环不变式证明算法是对的。它的作用类似审计里的"勾稽关系"：每一轮循环开始时都必须成立的一句话（比如"资产 = 负债 + 所有者权益"），只要开头成立、每轮都保持、结束时还成立，就能推出最终结果正确。

需要先想起来的数学

• 求和记号 \(\sum\)。 \(\sum_{j=2}^{n} j\) 表示把 \(j=2,3,\dots,n\) 代进去逐个相加。常用公式：\(1+2+\cdots+n=\frac{n(n+1)}{2}\)。例如 \(n=4\)：\(1+2+3+4=10=\frac{4\times5}{2}\)。本章用它把插入排序的"每轮比较次数"加总。详见 第 00 册第 07 章 概率中的分析工具。
• 对数 \(\lg n\)。 本书 \(\lg n=\log_2 n\)，意思是"\(n\) 要连续除以 2 多少次才变成 1"。\(\lg 8=3\)，\(\lg 1024=10\)，\(\lg 10^6\approx20\)。对数增长极慢：数据量乘 1000 倍，\(\lg n\) 只加约 10。这正是归并排序快的根源：一堆数对半劈，劈 \(\lg n\) 次就劈到单个元素。详见 第 00 册第 04 章 级数与收敛。
• 数学归纳法。 想证明一句话对所有 \(n=1,2,3,\dots\) 成立，只需两步：证明 \(n=1\) 时成立（基础步）；证明"若对 \(n\) 成立，则对 \(n+1\) 也成立"（归纳步）。像多米诺骨牌：第一块倒、每块都能推倒下一块，全部都倒。循环不变式就是它的变体。详见 第 00 册第 08 章 读懂数学证明与符号。
• 取整符号。 \(\lfloor x\rfloor\) 是向下取整（\(\lfloor 3.7\rfloor=3\)），\(\lceil x\rceil\) 是向上取整（\(\lceil 3.2\rceil=4\)）。7 个元素对半分，左边 \(\lceil 7/2\rceil=4\) 个，右边 \(\lfloor 7/2\rfloor=3\) 个。
• \(\Theta\) 记号的直观读法。 本章先把 \(\Theta(n^2)\) 读成"耗时大约和 \(n^2\) 成正比"即可，严格定义在第 03 章。详见 第 00 册第 07 章 概率中的分析工具 中"大 O 小 o"一节。

怎么读这一章

1.2 节的"计算机 A 与 B"例子和那张"1 秒到 1 年能处理多大问题"的表是全章的灵魂，一定要读懂。1.3 节（插入排序与循环不变式）和 1.5 节（归并排序与递归树）是核心，建议拿纸笔手动跑一遍原书例子。1.4 节的逐行代价表看起来繁琐，第一次读只需抓住结论："最好是线性、最坏是二次"。1.1 节和 1.6 节可以快速浏览，1.6 节的逆序对与"量化实战"里的 Kendall \(\tau\) 对因子研究很实用，值得回头细看。伪代码约定（1.3 节末）读不懂没关系，遇到具体代码时再回查。

Python 代码里有几处语法第一次见可能会卡：a[i] 的下标从 0 开始（不是伪代码的 1）；a[:mid] 表示"取前 mid 个元素"，a[mid:] 表示"从第 mid 个取到末尾"；lambda n: n**2 是一个临时的小函数，等价于"输入 \(n\)，返回 \(n^2\)"；// 是整除（\(7//2=3\)）。

1.1 什么是算法

定义

非形式地说，算法（algorithm）是任何良定义的计算过程：取某个值或值的集合作为输入（input），产生某个值或值的集合作为输出（output）。换个角度，算法是求解某个良说明的**计算问题（computational problem）**的工具：问题用一般性的语言规定输入和输出之间应满足的关系，算法给出实现这种关系的具体步骤。

最常用的例子是排序问题（sorting problem）：

• 输入：\(n\) 个数的序列 \(\langle a_1,a_2,\dots,a_n\rangle\)。
• 输出：输入序列的一个排列（重排）\(\langle a'_1,a'_2,\dots,a'_n\rangle\)，满足 \(a'_1\le a'_2\le\cdots\le a'_n\)。

给定输入 \(\langle 31,41,59,26,41,58\rangle\)，正确的排序算法输出 \(\langle 26,31,41,41,58,59\rangle\)。这样一个具体输入叫问题的一个实例（instance）。

排序是大量程序的中间步骤。哪种排序算法最好，取决于待排序的项数、数据已经部分有序的程度、键值可能的取值限制、计算机体系结构，以及数据放在内存、磁盘还是更慢的存储上。量化里也一样：对 5000 只股票做截面排名和对十年逐笔成交按时间排序，适用的方法不同。

正确性（correctness）。 如果对每个输入实例，算法都会停机并给出正确输出，就称这个算法是正确的，它**求解（solves）**了该问题。不正确的算法可能不停机，也可能停机但答案错。错误率可控的不正确算法有时也有用（原书第 31 章寻找大素数的算法就是例子），但全书主要讨论正确算法。

算法能解决哪些问题

原书列举了人类基因组测序、互联网路由与搜索、电子商务中的公钥密码与数字签名、制造与商业中的稀缺资源分配（钻井选址、广告投放、航空排班，都可以写成线性规划）。书中还会具体解决：

• 最短路径：把路网建模为图，求两点之间的最短路径（第 24 章）。可能的路径数量巨大。
• 最长公共子序列（LCS）：\(X\)、\(Y\) 分别有 \(2^m\)、\(2^n\) 个子序列，穷举不可行，第 15a 章用动态规划求解。
• 拓扑排序：\(n\) 个零件有 \(n!\) 种排列顺序，阶乘比指数增长还快，不能枚举（第 22 章）。
• 凸包：平面 \(n\) 个点的最小凸多边形，\(2^n\) 个子集都可能是顶点集（原书第 33 章，本册第 31 章第三部分）。

这些问题有两个共同点：候选解很多，绝大多数不是解，找到一个解或最好的解很有挑战；它们都有实际用途。也有问题没有明显的"候选解集合"，例如离散傅里叶变换（DFT），第 30 章的快速傅里叶变换（FFT）在信号处理、数据压缩和大数乘法里都有用。

**数据结构（data structure）**是存储和组织数据、以便访问和修改的方式。没有一种数据结构适合所有用途，所以要了解多种结构的长处与局限。

难解问题（hard problems）。 有一类问题至今没有已知的高效算法，称为 **NP 完全（NP-complete）**问题（第 34 章）。它们有三点值得记住：没人找到高效算法，也没人证明不存在；只要其中任何一个有高效算法，全部都有；有些 NP 完全问题和已有高效算法的问题非常相似，问题陈述稍作改动，最佳已知算法的效率就会剧变。实际意义是：一旦确认问题是 NP 完全的，就别再找精确的高效算法，转而设计"足够好但未必最优"的近似算法。旅行商问题（traveling-salesman problem）就是例子：送货卡车从仓库出发跑完所有点再回来，要最小化总路程。

并行（parallelism）。 功率密度随时钟频率超线性增长，芯片无法无限提频，于是转向多核。要用好多核，就得在设计算法时考虑并行，原书第 27 章给出多线程算法模型。

1.2 算法是一种技术

假如计算机无限快、内存免费，还要研究算法吗？仍然要，至少要证明方法会停机并给出正确答案。但现实中时间和空间都是有限资源，高效算法帮助我们合理使用它们。

效率差距压倒硬件差距

解同一问题的不同算法，效率差异常常比硬件差异更大。插入排序耗时约 \(c_1n^2\)，归并排序约 \(c_2n\lg n\)（本书 \(\lg n=\log_2 n\)），通常 \(c_1<c_2\)。把两者写成 \(c_1n\cdot n\) 与 \(c_2n\cdot\lg n\)，区别只在 \(n\) 与 \(\lg n\) 这一个因子：\(n=1000\) 时 \(\lg n\approx10\)，\(n=10^6\) 时 \(\lg n\approx20\)。小规模时插入排序常更快，但无论 \(c_1\) 比 \(c_2\) 小多少，总存在一个交叉点（crossover point），规模超过它之后归并排序就更快。

原书例子。 计算机 A 每秒执行 \(10^{10}\) 条指令，计算机 B 每秒 \(10^7\) 条，A 快 1000 倍。最好的程序员用机器语言在 A 上实现插入排序，需要 \(2n^2\) 条指令；普通程序员用低效编译器在 B 上实现归并排序，需要 \(50n\lg n\) 条指令。排序 \(n=10^7\) 个数：

慢 1000 倍的机器反而快了 17 倍以上。排 1 亿个数时，插入排序要 23 天以上，归并排序不到 4 小时。问题越大，增长慢的算法优势越大。

白话解释：把公式拆开看。A 的耗时 = 指令条数 ÷ 每秒速度 = \(2n^2/10^{10}\)；B 的耗时 = \(50n\lg n/10^7\)。\(n=10^7\) 时 \(\lg 10^7\approx23.25\)，所以 B 是 \(50\times10^7\times23.25/10^7\approx1163\) 秒。关键在于：A 的耗时随 \(n^2\) 涨，数据翻倍耗时乘 4；B 的耗时随 \(n\lg n\) 涨，数据翻倍耗时只乘 2 点几。硬件快 1000 倍是一次性的"常数倍"优势，而 \(n\) 与 \(\lg n\) 之比会随规模无限拉大（\(n=10^7\) 时已经是 43 万倍），常数倍迟早被吃掉。这像比较两只基金：一只前端申购费打一折（一次性的常数优势），另一只每年管理费低 1%（随期限不断累积的差距），期限够长，后者一定胜出。

不同增长率在固定时间预算内能处理多大的问题

原书思考题 1-1 问：若算法耗时 \(f(n)\) 微秒，在 1 秒、1 小时、1 天、1 年内能解的最大 \(n\) 是多少？下面的程序用"倍增 + 二分查找"直接求出答案（二分查找见 1.6 节）。

import math
# 思考题 1-1：耗时 f(n) 微秒的算法，在时间预算 t 内能处理的最大规模 n
budgets = {"1秒": 1e6, "1小时": 3.6e9, "1天": 8.64e10, "1年": 3.15576e13}
funcs = {
    "n lg n": lambda n: n * math.log2(n),
    "n^2": lambda n: n**2,
    "n^3": lambda n: n**3,
    "2^n": lambda n: 2.0**n,
    "n!": lambda n: math.factorial(n),
}
def max_n(f, t):
    lo, hi = 1, 2
    while f(hi) <= t:            # 倍增找到一个超出预算的 hi
        lo, hi = hi, hi * 2
    while hi - lo > 1:           # 在 [lo, hi) 上二分
        mid = (lo + hi) // 2
        lo, hi = (mid, hi) if f(mid) <= t else (lo, mid)
    return lo
print(f"{'f(n)':8s}" + "".join(f"{k:>18s}" for k in budgets))
for name, f in funcs.items():
    print(f"{name:8s}" + "".join(f"{max_n(f, t):>18,d}" for t in budgets.values()))
ok = [n for n in range(2, 100) if 8*n*n < 64*n*math.log2(n)]
print("练习1.2-2 插入排序更快的 n:", ok[0], "~", ok[-1])
print("练习1.2-3 最小 n:", min(n for n in range(1, 100) if 100*n*n < 2**n))

输出：

f(n)                    1秒               1小时                1天                1年
n lg n              62,746       133,378,058     2,755,147,513   798,160,978,351
n^2                  1,000            60,000           293,938         5,617,615
n^3                    100             1,532             4,420            31,601
2^n                     19                31                36                44
n!                       9                12                13                16
练习1.2-2 插入排序更快的 n: 2 ~ 43
练习1.2-3 最小 n: 15

读这张表要看两点。第一，时间预算从 1 秒放大到 1 年（约 \(3\times10^7\) 倍），\(n\lg n\) 算法能处理的规模也放大了约 \(10^7\) 倍，\(n^2\) 只放大约 5600 倍，\(2^n\) 只从 19 涨到 44。指数算法几乎不能靠加机器、加时间来扩展。第二，练习 1.2-2 说明，同一台机器上插入排序 \(8n^2\) 步、归并排序 \(64n\lg n\) 步时，只有 \(2\le n\le43\) 时插入排序更快，这就是交叉点。

白话解释：用"数据量翻倍，耗时翻几倍"来记这几类增长最省事。\(n\lg n\)：翻倍后耗时略多于 2 倍；\(n^2\)：4 倍；\(n^3\)：8 倍；\(2^n\)：\(n\) 只要加 1 耗时就翻倍，\(n\) 翻倍则耗时变成原来的平方；\(n!\) 比这还快。反过来读就是表里的现象：预算多给 \(3\times10^7\) 倍，\(n^2\) 算法的规模只能扩大 \(\sqrt{3\times10^7}\approx5600\) 倍，\(2^n\) 算法只能多处理 \(\lg(3\times10^7)\approx25\) 个元素。

代码说明：max_n 先把 hi 不断乘 2，直到耗时超出预算，再在 lo 与 hi 之间对半试探（就是 1.6 节的二分查找），所以能很快找到"刚好不超预算的最大 \(n\)"。f"{x:>18,d}" 只是排版格式：右对齐、宽 18 位、加千分位逗号。

算法与其他技术

即使应用本身看不出算法（例如一个简单 Web 应用），它依赖的硬件设计、图形界面、网络路由、编译器也都大量使用算法。计算机越快，我们越会去解更大的问题，而恰恰在大规模下算法效率的差距最显著。

1.3 插入排序与循环不变式

算法

**插入排序（insertion sort）**适合少量元素，过程像整理手里的扑克牌：左手起初为空，每次从桌上摸一张，从右往左和手中的牌比较，插到正确位置。任何时刻左手的牌都已排好序，而且正是原牌堆顶部的那几张。

原书伪代码下标从 1 开始，数组 \(A[1..n]\)：

INSERTION-SORT(A)
1  for j = 2 to A.length
2      key = A[j]
3      // 把 A[j] 插入已排好序的 A[1..j-1]
4      i = j - 1
5      while i > 0 and A[i] > key
6          A[i+1] = A[i]
7          i = i - 1
8      A[i+1] = key

插入排序是原地（in place）排序：任何时刻至多常数个元素存放在数组之外。它也是稳定的：第 5 行用严格的 >，相等元素不会越过彼此。

例（原书图 2.2）。 \(A=\langle5,2,4,6,1,3\rangle\)，每轮外层循环后依次得到 \(\langle2,5,4,6,1,3\rangle\)、\(\langle2,4,5,6,1,3\rangle\)、\(\langle2,4,5,6,1,3\rangle\)、\(\langle1,2,4,5,6,3\rangle\)、\(\langle1,2,3,4,5,6\rangle\)。

用循环不变式证明正确性

循环不变式（loop invariant）：在第 1–8 行 for 循环每次迭代开始时，子数组 \(A[1..j-1]\) 由原来在 \(A[1..j-1]\) 中的元素组成，并且已按序排列。

证明一个循环不变式要做三件事：

• 初始化（Initialization）：第一次迭代前它为真。
• 保持（Maintenance）：如果某次迭代前它为真，下次迭代前它仍为真。
• 终止（Termination）：循环结束时，不变式与"循环为何结束"结合起来，给出一个有助于证明算法正确的性质。

前两条相当于数学归纳法的基础步和归纳步。第三条是最关键的区别：普通归纳法无限进行下去，这里的"归纳"在循环终止时停下，并且要用到终止条件。

对插入排序：

• 初始化：\(j=2\)，\(A[1..1]\) 只有原来的 \(A[1]\)，单个元素自然有序。
• 保持：循环体把 \(A[j-1],A[j-2],\dots\) 依次右移一格，直到找到 \(A[j]\) 的位置再放入，于是 \(A[1..j]\) 由原 \(A[1..j]\) 的元素有序组成；\(j\) 加 1 后不变式恢复。（严格的证明还要为内层 while 循环另立一个不变式，原书从略。）
• 终止：for 循环在 \(j>n\) 时结束，此时 \(j=n+1\)。代入不变式，\(A[1..n]\) 由原 \(A[1..n]\) 的元素有序组成，即整个数组已排好序。

金融直觉：循环不变式很像月末对账。"初始化"是开账时期初余额核对无误；"保持"是证明每记一笔分录后，试算平衡依旧成立；"终止"是年末关账时，把"试算平衡"和"所有凭证都已入账"这两件事合起来，推出年报正确。对插入排序，那句"试算平衡"就是"左边 \(j-1\) 张牌已经排好"；"所有凭证都已入账"就是 \(j=n+1\)，即所有牌都摸完了。两句话合起来，正好是"整副牌排好了"。

注意"for 循环结束后计数器等于第一个超过上界的值"这一约定，证明里的 \(j=n+1\) 正是来自它。对 for 循环，"第一次迭代前"指计数器赋初值之后、第一次检查循环条件之前。

练习 2.1-3 让读者对线性查找做同样的证明：不变式是"每次迭代开始时，\(A[1..i-1]\) 中没有 \(v\)"；若在第 \(i\) 处找到就返回 \(i\)，若循环结束（\(i=n+1\)），不变式说明整个数组中都没有 \(v\)，返回 NIL 是对的。

伪代码约定（第 3 版）

原书伪代码与 C、Java、Python 相近，掌握以下几条即可读懂全书：缩进表示块结构；for ... to 递增、downto 递减；// 是注释；= 赋值、== 判等；变量是过程局部的；数组用 \(A[i]\) 访问，\(A[1..j]\) 表示子数组；对象属性用点号，如 A.length；表示数组或对象的变量是指针，y = x 后两者指向同一对象，空指针为 NIL；参数按值传递，但传对象时复制的是指针，所以修改 x.f 对调用者可见；and、or 短路求值；return 可同时返回多个值；error 表示调用条件不满足。

1.4 分析算法

RAM 模型

分析算法就是预测它需要的资源，最常见的是计算时间。为此需要一个计算模型。全书采用**随机访问机（random-access machine, RAM）**模型：单处理器，指令逐条执行，没有并发。常见指令（加减乘除、取余、floor、ceiling，load、store、copy，条件与无条件跳转、子程序调用与返回）各耗常数时间。数据类型是整数和浮点数。字长有限：输入规模为 \(n\) 时，整数用 \(c\lg n\) 位表示（\(c\ge1\) 为常数）。\(c\ge1\) 保证一个字能存下 \(n\)、能索引所有元素；\(c\) 为常数则防止"一个字里塞下海量数据并常数时间处理"这种不现实的情况。

模型有灰色地带。一般的求幂 \(x^y\) 不是常数时间，但 \(2^k\) 可以由左移 \(k\) 位得到，所以 \(k\) 不超过字长时视为常数时间。RAM 模型也不模拟 cache 和虚拟内存。在量化系统里，cache 命中率和内存带宽常常是真正的瓶颈（例如按行还是按列遍历一个大 DataFrame），这时 RAM 分析只能给出量级判断，最后还要实测。

白话解释：RAM 模型是一套"记账准则"。不同电脑速度不同，直接比秒数没有意义，就像不同国家的财报不能直接比金额。于是约定：每做一次加法、比较、读写一个数，都记"1 笔"（耗时一个常数）。有了统一口径，才能比较算法本身的好坏。"字长 \(c\lg n\) 位"这个细节只是为了堵住作弊：不允许把一百万个数塞进一个变量里一步算完。第一次读可以跳过。

**输入规模（input size）**依问题而定：排序用元素个数 \(n\)；整数乘法用输入的总位数；图用顶点数和边数两个参数。**运行时间（running time）**是在特定输入上执行的基本操作数。约定伪代码第 \(i\) 行每执行一次耗常数时间 \(c_i\)；调用子程序这一行本身是常数时间，被调过程的时间另算。

插入排序的精确分析

对 \(j=2,\dots,n\)，令 \(t_j\) 为第 5 行 while 条件对该 \(j\) 被测试的次数。循环正常退出时，条件比循环体多测试一次。

总运行时间是"代价 × 次数"之和：

最好情况是输入已排好序：每次第 5 行一测就失败，\(t_j=1\)，

形如 \(an+b\)，是 \(n\) 的线性函数。

最坏情况是输入逆序：\(A[j]\) 要和 \(A[1..j-1]\) 中每个元素比较，\(t_j=j\)。利用 \(\sum_{j=2}^n j=\frac{n(n+1)}{2}-1\) 与 \(\sum_{j=2}^n(j-1)=\frac{n(n-1)}{2}\)，

形如 \(an^2+bn+c\)，是二次函数。

推导拆解：从总式到最坏情况只做了三件事。 第一步，代入 \(t_j=j\)：第 5 行的次数变成 \(\sum_{j=2}^n j\)，第 6、7 行变成 \(\sum_{j=2}^n (j-1)\)。 第二步，套求和公式。\(\sum_{j=2}^n j\) 是"\(1+2+\cdots+n\) 去掉开头的 1"，所以等于 \(\frac{n(n+1)}{2}-1\)；\(\sum_{j=2}^n(j-1)=1+2+\cdots+(n-1)=\frac{(n-1)n}{2}\)。 第三步，展开合并同类项。\(c_5\big(\frac{n^2+n}{2}-1\big)\) 贡献 \(\frac{c_5}{2}n^2+\frac{c_5}{2}n-c_5\)；\((c_6+c_7)\frac{n^2-n}{2}\) 贡献 \(\frac{c_6+c_7}{2}n^2-\frac{c_6+c_7}{2}n\)；其余各项都是 \(c\cdot n\) 或 \(c\cdot(n-1)\)。把 \(n^2\)、\(n\)、常数三类分别收集，就是上式。 记住结论比记住系数重要：每轮要比较的次数从 1 涨到 \(n\)，平均约 \(n/2\)，一共 \(n\) 轮，所以总量约 \(n^2/2\)，是二次的。数一下 \(n=4\) 的逆序数组 \(\langle4,3,2,1\rangle\)：第 6 行右移次数为 \(1+2+3=6=\frac{4\times3}{2}\)。

为什么通常只看最坏情况

全书主要求最坏情况运行时间，理由有三：它是任何输入的上界，是一种保证；有些算法的最坏情况经常出现，例如数据库里查找不存在的记录；平均情况往往和最坏情况一样差。比如随机输入的插入排序，平均而言 \(A[1..j-1]\) 中一半元素比 \(A[j]\) 大，\(t_j\approx j/2\)，平均运行时间仍是二次的。平均情况分析的难点在于"平均输入"是什么并不清楚，通常假设所有同规模输入等可能，这在现实中未必成立；第 5 章会用随机算法绕开这个问题。

练习 2.2-4 指出另一面：几乎任何算法都能通过"遇到某个特定输入就直接输出预先算好的答案"获得很好的最好情况运行时间，所以最好情况意义不大。

增长量级

再做两步抽象：只保留最高阶项（低阶项在大 \(n\) 时可以忽略），并去掉最高阶项的系数（常数因子在大输入时不如增长率重要）。于是插入排序最坏情况运行时间是 \(\Theta(n^2)\)。\(\Theta\) 的精确定义见第 03 章。一个算法最坏情况的**增长量级（order of growth）**更低，通常就认为它更有效。小输入时结论可能相反，但输入足够大时，\(\Theta(n^2)\) 算法在最坏情况下总快于 \(\Theta(n^3)\) 算法。

练习 2.2-1：\(n^3/1000-100n^2-100n+3=\Theta(n^3)\)。练习 2.2-2 的**选择排序（selection sort）**每次找出剩余最小元素与 \(A[i]\) 交换，不变式是"\(A[1..i-1]\) 是全数组最小的 \(i-1\) 个元素且有序"，只需对前 \(n-1\) 个位置做（最后一个自然是最大的），最好与最坏都是 \(\Theta(n^2)\)。练习 2.2-3：线性查找在目标等可能出现在任一位置时平均检查 \((n+1)/2\) 个元素，最坏 \(n\) 个，两者都是 \(\Theta(n)\)。

1.5 分治法与归并排序

插入排序用的是增量法（incremental approach）：排好 \(A[1..j-1]\) 后插入 \(A[j]\)。下面介绍另一种设计方法。

分治法的三步

很多算法是**递归（recursive）**的：为了解决问题，调用自身去解若干个相关的子问题。**分治法（divide-and-conquer）**在每层递归上有三步：

• 分解（Divide）：把问题分成若干个规模更小的同类子问题；
• 解决（Conquer）：递归求解子问题，子问题足够小时直接求解；
• 合并（Combine）：把子问题的解合并成原问题的解。

归并排序（merge sort）：把 \(n\) 个元素分成各含 \(n/2\) 个元素的两半；递归地排好两半；把两个有序子序列归并成一个。序列长度为 1 时递归"触底"，长度 1 的序列天然有序。

白话解释：递归第一次接触时最容易困惑的是"一个方法还没写完，怎么能调用它自己"。秘诀是：调用自己时，问题一定变小了，并且有一个小到不用再算的"底"。想象一位经理要把 8 份报表按日期排好：他把报表分成两叠各 4 份，交给两个下属"用同样的方法排好再交回"；下属又各分成 2 份交给更下一级……到只剩 1 份时，那个人什么都不用做，直接交回。然后每一级只做一件事：把两叠已排好的报表合并成一叠。整个过程里，没有任何一个人需要"一次性排好 8 份"，每个人只做"拆分"和"合并"。写递归程序时，你只需要保证两点：触底的情况处理对了；假设"小一号的问题已经被正确解决"，能把它们拼成大问题的答案。这和数学归纳法的结构完全一样。

MERGE 过程

关键是合并步骤。MERGE\((A,p,q,r)\) 中 \(p\le q<r\)，假定 \(A[p..q]\) 与 \(A[q+1..r]\) 都已有序，把它们归并成有序的 \(A[p..r]\)。直观上像桌上两堆面朝上、各自有序、最小牌在顶的扑克：每一步拿起两堆顶上较小的一张放到输出堆，一堆空了就把另一堆整个放上去。每步常数时间，最多 \(n=r-p+1\) 步，所以 MERGE 是 \(\Theta(n)\)。

原书用了**哨兵（sentinel）**技巧：在两堆底部各放一张值为 \(\infty\) 的牌，这样不必每步检查某一堆是否已空。露出 \(\infty\) 的那堆不可能被选中，除非两堆都只剩哨兵，而那时所有真牌已经输出完毕，恰好执行了 \(r-p+1\) 步。

MERGE(A, p, q, r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  令 L[1..n1+1] 与 R[1..n2+1] 为新数组
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = ∞
 9  R[n2 + 1] = ∞
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j]          // 用 <= 保证稳定
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

例（原书图 2.3）。 MERGE\((A,9,12,16)\)，\(A[9..16]=\langle2,4,5,7,1,2,3,6\rangle\)。复制后 \(L=\langle2,4,5,7,\infty\rangle\)，\(R=\langle1,2,3,6,\infty\rangle\)，依次输出 \(1,2,2,3,4,5,6,7\)，结束时 \(L\)、\(R\) 中只剩两个哨兵。

MERGE 的循环不变式（第 12–17 行）：每次迭代开始时，\(A[p..k-1]\) 按序包含 \(L[1..n_1+1]\) 和 \(R[1..n_2+1]\) 中最小的 \(k-p\) 个元素；并且 \(L[i]\)、\(R[j]\) 分别是各自数组中尚未复制回 \(A\) 的最小元素。

• 初始化：\(k=p\)，\(A[p..k-1]\) 为空，含 0 个最小元素；\(i=j=1\)，\(L[1]\)、\(R[1]\) 是各自最小的未复制元素。
• 保持：设 \(L[i]\le R[j]\)，则 \(L[i]\) 是所有未复制元素中最小的。把它复制到 \(A[k]\) 后，\(A[p..k]\) 含最小的 \(k-p+1\) 个元素；\(k\) 和 \(i\) 各加 1，不变式恢复。\(L[i]>R[j]\) 时对称。
• 终止：\(k=r+1\)，\(A[p..r]\) 按序包含最小的 \(r-p+1\) 个元素。\(L\)、\(R\) 共有 \(n_1+n_2+2=r-p+3\) 个元素，除两个最大的（哨兵）外都已复制回去。

时间：第 1–3、8–11 行常数；第 4–7 行 \(\Theta(n_1+n_2)=\Theta(n)\)；第 12–17 行 \(n\) 次迭代、每次常数。总计 \(\Theta(n)\)，额外空间 \(\Theta(n)\)。

练习 2.3-2 要求去掉哨兵：当 \(L\) 或 \(R\) 之一全部复制完后，把另一个的剩余部分直接拷回 \(A\)。实际编程（包括后面的 Python 代码）多用这种写法，因为浮点数据里的 \(\infty\) 可能与真实数据冲突。

MERGE-SORT

MERGE-SORT(A, p, r)
1  if p < r
2      q = ⌊(p + r)/2⌋
3      MERGE-SORT(A, p, q)
4      MERGE-SORT(A, q + 1, r)
5      MERGE(A, p, q, r)

初始调用 MERGE-SORT\((A,1,A.length)\)。\(p\ge r\) 时子数组至多一个元素，已经有序。取 \(q=\lfloor(p+r)/2\rfloor\) 使左右两段大小分别为 \(\lceil n/2\rceil\) 与 \(\lfloor n/2\rfloor\)。

例（原书图 2.4）。 \(A=\langle5,2,4,7,1,3,2,6\rangle\)，自底向上看：两两归并得 \(\langle2,5\rangle,\langle4,7\rangle,\langle1,3\rangle,\langle2,6\rangle\)，再得 \(\langle2,4,5,7\rangle,\langle1,2,3,6\rangle\)，最后得 \(\langle1,2,2,3,4,5,6,7\rangle\)。

归并排序的性质：时间在最好、最坏、平均情况下都是 \(\Theta(n\lg n)\)；需要 \(\Theta(n)\) 辅助数组和 \(\Theta(\lg n)\) 递归栈；稳定；不是原地排序。

分析分治算法：递归式与递归树

当算法递归调用自身时，运行时间常用**递归式（recurrence）**描述：用较小输入上的运行时间表示规模 \(n\) 上的运行时间。设规模足够小（\(n\le c\)）时直接求解需 \(\Theta(1)\)；否则分成 \(a\) 个子问题，每个规模为原来的 \(1/b\)，分解耗时 \(D(n)\)，合并耗时 \(C(n)\)：

归并排序中 \(a=b=2\)（很多分治算法 \(a\ne b\)）。为简化，假设 \(n\) 是 2 的幂（第 04b 章说明这不影响增长量级）。分解只算中点，\(D(n)=\Theta(1)\)；解决两个规模 \(n/2\) 的子问题贡献 \(2T(n/2)\)；合并 \(C(n)=\Theta(n)\)。于是

用一个常数 \(c\) 同时代表"解规模 1 问题的时间"和"分解、合并时每个元素的时间"，改写为

（若两个常数不同，取较大者得上界、较小者得下界，二者都是 \(n\lg n\) 量级。）

递归树。 根的代价是 \(cn\)，它有两棵子树 \(T(n/2)\)；继续展开，第 \(i\) 层（根为第 0 层）有 \(2^i\) 个结点，每个代价 \(c(n/2^i)\)，该层合计 \(2^i\cdot c(n/2^i)=cn\)。最底层 \(n\) 个叶子各代价 \(c\)，合计也是 \(cn\)。树共有 \(\lg n+1\) 层：\(n=1\) 时 1 层；若 \(2^i\) 个叶子的树有 \(i+1\) 层，\(2^{i+1}\) 个叶子的树多一层，有 \((i+1)+1=\lg2^{i+1}+1\) 层。所以

推导拆解：递归树就是把"谁花了多少时间"画成一张组织架构图，再按层加总。以 \(n=8\) 为例： 第 0 层：1 个结点，处理 8 个元素，合并代价 \(8c\)。 第 1 层：2 个结点，各处理 4 个，代价 \(2\times4c=8c\)。 第 2 层：4 个结点，各处理 2 个，代价 \(4\times2c=8c\)。 第 3 层：8 个叶子，各 1 个元素，代价 \(8\times c=8c\)。 每层都是 \(8c=cn\)，因为"结点数翻倍、每个结点的规模减半"正好抵消。层数是 \(\lg 8+1=4\)。总计 \(4\times8c=32c=cn(\lg n+1)\)。 数据翻倍到 \(n=16\)：每层代价翻倍成 \(16c\)，层数只多一层变成 5，总计 \(80c\)，是原来的 2.5 倍，"略多于 2 倍"。这就是 \(n\lg n\) 的样子。递归式 (2.2) 本身读作："排 \(n\) 个数的时间 = 排两个 \(n/2\) 的时间 + 合并的 \(cn\)"。

练习 2.3-3 用数学归纳法严格证明：\(n\) 为 2 的幂时，\(T(2)=2\)、\(T(n)=2T(n/2)+n\) 的解为 \(T(n)=n\lg n\)。归纳步为 \(T(2^{k+1})=2\cdot2^kk+2^{k+1}=2^{k+1}(k+1)\)。

1.6 几个延伸问题

原书第 2 章的练习和思考题包含几个后面常用的结论，这里集中讲。

二分查找（binary search，练习 2.3-5）。 在有序数组中找 \(v\)：把中点与 \(v\) 比较，每次排除一半。递归式 \(T(n)=T(n/2)+\Theta(1)\)，最坏 \(\Theta(\lg n)\)。在量化系统中，它对应在有序时间戳上定位，例如 as-of join（找每个信号时刻之前最近的一笔报价）和按时间切片，numpy.searchsorted、bisect 模块和 pandas.merge_asof 都基于它。

内层用二分查找能否让插入排序变成 \(\Theta(n\lg n)\)（练习 2.3-6）？ 不能。比较次数降到 \(O(n\lg n)\)，但找到位置后仍要把元素逐个右移，移动次数在最坏情况下仍是 \(\Theta(n^2)\)。

两数之和（练习 2.3-7）。 给定 \(n\) 个整数的集合 \(S\) 和整数 \(x\)，判断是否存在两个元素之和恰为 \(x\)。先排序（\(\Theta(n\lg n)\)），再用双指针从两端向中间扫描（\(\Theta(n)\)），或对每个元素二分查找 \(x-s\)。总时间 \(\Theta(n\lg n)\)。

在归并排序中对小数组改用插入排序（思考题 2-1）。 先用插入排序分别排好 \(n/k\) 个长度为 \(k\) 的子表，需 \(\Theta(nk)\)；再归并，归并树有 \(\lg(n/k)\) 层、每层 \(\Theta(n)\)，需 \(\Theta(n\lg(n/k))\)。总时间 \(\Theta(nk+n\lg(n/k))\)。要与标准归并排序同阶，\(k\) 最大可取 \(\Theta(\lg n)\)；实践中 \(k\) 取"插入排序比归并排序快的最大规模"，要实测。这就是"粗化递归叶子"的思想，Python 的 Timsort、C++ 的 introsort 都这么做。

冒泡排序（思考题 2-2）。 证明排序算法正确，除了输出有序，还要证明输出是输入的一个排列。冒泡排序的内层循环不变式是"每次迭代开始时 \(A[j]\) 是 \(A[j..n]\) 中的最小元素，且 \(A[j..n]\) 是原元素的排列"，外层是"\(A[1..i-1]\) 由全数组最小的 \(i-1\) 个元素有序组成"。它的最坏运行时间与插入排序同为 \(\Theta(n^2)\)，但最好情况也是 \(\Theta(n^2)\)，比较次数固定为 \(n(n-1)/2\)。

霍纳规则（Horner's rule，思考题 2-3）。

代码为 y = 0; for i = n downto 0: y = a_i + x*y，运行时间 \(\Theta(n)\)；从头计算每一项（第 \(k\) 项要 \(k\) 次乘法）是 \(\Theta(n^2)\)。循环不变式：每次迭代开始时 \(y=\sum_{k=0}^{n-(i+1)}a_{k+i+1}x^k\)（空和为 0）。终止时 \(i=-1\)，得 \(y=\sum_{k=0}^na_kx^k\)。

逆序对（inversions，思考题 2-4）。 \(A[1..n]\) 为 \(n\) 个不同的数，若 \(i<j\) 且 \(A[i]>A[j]\)，称 \((i,j)\) 为一个逆序对。例：\(\langle2,3,8,6,1\rangle\) 有 5 个逆序对 \((1,5),(2,5),(3,4),(3,5),(4,5)\)。元素取自 \(\{1,\dots,n\}\) 时逆序排列的逆序对最多，为 \(\binom n2=n(n-1)/2\) 个。两个重要结论：

1. 插入排序第 6 行（右移）的执行次数恰好等于逆序对数 \(I\)，所以插入排序运行时间是 \(\Theta(n+I)\)。数据"几乎有序"时它几乎是线性的。
2. 修改归并排序可以在 \(\Theta(n\lg n)\) 时间内统计逆序对：归并时每当从 \(R\) 取出一个元素，它比 \(L\) 中剩下的 \(n_1-i+1\) 个元素都小，把这个数加到计数器上。

推导拆解：为什么从 \(R\) 取一个元素就能一次记上一批逆序对？用 \(\langle2,3,8,6,1\rangle\) 走一遍（按后面 Python 代码的分法）。先劈成左半 \(\langle2,3\rangle\) 和右半 \(\langle8,6,1\rangle\)。递归数出左半内部 0 个、右半内部 3 个（\((8,6),(8,1),(6,1)\)），并把两半各自排好：\(L=\langle2,3\rangle\)，\(R=\langle1,6,8\rangle\)。现在只差"一个在左半、一个在右半"的逆序对。归并时先比较 2 和 1，取出 \(R\) 的 1：\(L\) 里还剩 2、3 两个，它们在原数组里都排在 1 前面且都比 1 大，一下子记 2 个。之后 2、3 被取出，\(L\) 空了，6 和 8 不再贡献。合计 \(0+3+2=5\)，与正文一致。 关键点是：\(L\) 已排好序，所以"\(L\) 中剩下的都比当前 \(R[j]\) 大"不必逐个比较就能确定。每次归并只花线性时间，却能一次数清跨两半的所有逆序对，这就省掉了两两枚举。排序在这里只是工具，副产品才是我们要的计数。

量化实战：排序、逆序对与秩相关

场景一：Kendall \(\tau\) 与因子 IC。 因子研究中常用秩相关衡量因子值与下期收益的单调关系。Spearman 相关最常见，Kendall \(\tau\) 对异常值更稳健、解释更直接：它等于"一致对"与"不一致对"比例之差。把股票按因子值排好序后，收益序列中的每个逆序对恰好是一个不一致对。无并列时

直接枚举所有对是 \(\Theta(n^2)\)，用归并排序数逆序对是 \(\Theta(n\lg n)\)（这就是 Knight 1966 年算法的核心思想）。全市场 5000 只股票时，两两枚举约 \(1.25\times10^7\) 对，而 \(n\lg n\approx6\times10^4\)，每天都算、回测 20 年，两种做法的计算量相差约两百倍。

场景二：几乎有序的数据用插入式维护。 多个交易所或多个线程推送的成交记录按时间戳到达，但会有少量乱序（晚到几毫秒）。此时逆序对数 \(I\) 很小，插入排序的 \(\Theta(n+I)\) 远好于每次全量重排。

import numpy as np
from scipy.stats import kendalltau

def insertion_sort(a):
    """返回 (排序结果, 右移次数)。右移次数恰好等于逆序对数 I。"""
    a = list(a); shifts = 0
    for j in range(1, len(a)):
        key, i = a[j], j - 1
        while i >= 0 and a[i] > key:       # 不变式: a[0..j-1] 有序
            a[i + 1] = a[i]; i -= 1; shifts += 1
        a[i + 1] = key
    return a, shifts

def sort_count(a):
    """归并排序并统计逆序对（思考题 2-4(d)），Θ(n lg n)。"""
    n = len(a)
    if n <= 1:
        return list(a), 0
    mid = n // 2
    L, x = sort_count(a[:mid])
    R, y = sort_count(a[mid:])
    out, i, j, inv = [], 0, 0, x + y
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            out.append(L[i]); i += 1
        else:                               # R[j] 比 L 中剩余 len(L)-i 个元素都小
            out.append(R[j]); j += 1; inv += len(L) - i
    out += L[i:] + R[j:]
    return out, inv

# 1) 原书例子与思考题 2-4(a)
print(insertion_sort([5, 2, 4, 6, 1, 3]))
print("逆序对 <2,3,8,6,1>:", sort_count([2, 3, 8, 6, 1])[1])

# 2) 量化场景：因子值与下期收益的 Kendall tau（秩 IC 的一种）
rng = np.random.default_rng(42)
n = 3000                                     # 截面股票数
factor = rng.standard_normal(n)
ret = 0.05 * factor + rng.standard_normal(n) # 弱预测力
order = np.argsort(factor)                   # 按因子排好序后看收益序列的逆序对
_, I = sort_count(list(ret[order]))
tau = 1 - 4 * I / (n * (n - 1))
print(f"逆序对 I={I}, 自算 tau={tau:.6f}, scipy tau={kendalltau(factor, ret)[0]:.6f}")

# 3) 插入排序对“几乎有序”数据很快：成交记录按时间戳到达但有少量乱序
ts = np.arange(20000, dtype=float)
noisy = ts + rng.integers(0, 3, size=ts.size)   # 每条记录最多延迟 2 个单位
_, shifts = insertion_sort(noisy)
print(f"n={ts.size}, 右移次数 I={shifts}, n^2/4≈{ts.size**2//4}")

输出：

([1, 2, 3, 4, 5, 6], 9)
逆序对 <2,3,8,6,1>: 5
逆序对 I=2187514, 自算 tau=0.027447, scipy tau=0.027447
n=20000, 右移次数 I=2245, n^2/4≈100000000

金融直觉：一致对就是"因子值高的那只，下期收益也高"的股票对；不一致对相反。按因子值从小到大排好后，如果收益序列也从小到大，那就没有逆序对，\(\tau=1\)，因子完美预测排名；逆序对越多，预测越差。公式 \(1-\frac{4I}{n(n-1)}\) 来自：总对数 \(\binom n2=\frac{n(n-1)}{2}\)，不一致对 \(I\) 个，一致对 \(\binom n2-I\) 个，差除以总数就是 \(1-\frac{2I}{\binom n2}\)。

代码说明：def f(a): 定义一个函数；return a, shifts 一次返回两个值，调用处用 L, x = sort_count(...) 分别接住。sort_count 在函数体里调用了它自己，这就是递归，if n <= 1 是触底的条件。np.argsort(factor) 返回"把因子从小到大排好时各股票的原始位置"，ret[order] 就是按因子排序后的收益序列。out += L[i:] + R[j:] 对应"一堆空了就把另一堆整个放上去"。

第一行中右移 9 次，正是 \(\langle5,2,4,6,1,3\rangle\) 的逆序对数。第三行显示，\(2\times10^4\) 条轻微乱序记录只需右移 2245 次，而随机顺序的期望逆序对数是 \(n(n-1)/4\approx10^8\)（第 05 章练习 5.2-5）。

其他对应关系。

• 多路归并。 把多个交易所、多个品种各自按时间排序的行情合并成一条时间线，是 MERGE 的推广。\(k\) 路归并借助堆可做到 \(O(n\lg k)\)（堆见本册第 06 章），Python 的 heapq.merge 就是这样实现的。
• 循环不变式用于回测引擎。 回测引擎的每个 bar 循环都应有明确的不变式，例如"每个 bar 开始时，现金 + 持仓市值 = 上一 bar 结束时的净值，且持仓只包含已成交订单"。写单元测试时，在每次迭代开头断言这些不变式，比只检查最终收益曲线更容易定位错误。
• 霍纳规则。 用多项式拟合的收益率曲线、期权定价中的多项式近似，求值都应当用霍纳形式，既快又减少舍入误差。

本章小结

算法是把输入变成输出的良定义计算过程，正确的算法对每个实例都停机并给出正确输出。证明迭代算法正确的标准工具是循环不变式，它是"在循环结束处停下"的数学归纳法。分析算法时采用 RAM 模型，按"每行代价 × 执行次数"求和，再只保留最高阶项、去掉常系数，得到增长量级。插入排序原地、稳定，最好 \(\Theta(n)\)，最坏 \(\Theta(n^2)\)，一般地是 \(\Theta(n+I)\)。归并排序用分治法设计，递归式 \(T(n)=2T(n/2)+\Theta(n)\)，递归树每层代价 \(cn\)、共 \(\lg n+1\) 层，总计 \(\Theta(n\lg n)\)。增长率的差异在大规模时压倒常数因子和硬件差距，但两个算法之间总有交叉点，小规模时简单算法可能更快，这正是混合排序"粗化叶子"的依据。

练习

基础

1. 仿照图 2.2，手工演示插入排序处理 \(\langle31,41,59,26,41,58\rangle\) 的每一步；再改写算法使其按非升序排序。 提示：只需把第 5 行的 A[i] > key 改为 A[i] < key。
2. 写出线性查找的伪代码，并用循环不变式证明它正确。 提示：不变式为"迭代开始时 \(A[1..i-1]\) 中不含 \(v\)"；终止时 \(i=n+1\)。
3. 同一台机器上插入排序需 \(8n^2\) 步、归并排序需 \(64n\lg n\) 步，\(n\) 为何值时插入排序更快？求使 \(100n^2\) 快于 \(2^n\) 的最小 \(n\)。 答案：\(2\le n\le43\)；\(n=15\)。
4. 用数学归纳法证明：\(n\) 为 2 的幂时，\(T(2)=2\)、\(T(n)=2T(n/2)+n\) 的解为 \(T(n)=n\lg n\)。
5. 递归版插入排序先递归排好 \(A[1..n-1]\)，再把 \(A[n]\) 插入。写出它的最坏情况递归式并求解。 答案：\(T(n)=T(n-1)+\Theta(n)\)，解为 \(\Theta(n^2)\)。
6. 不用哨兵改写 MERGE，并说明为什么在浮点行情数据上这种写法更稳妥。

进阶

7. 给定 \(n\) 个整数的集合 \(S\) 和整数 \(x\)，设计 \(\Theta(n\lg n)\) 算法判断是否存在两元素之和为 \(x\)。把它改写为"在一组股票的昨日收益中，找出两只收益之差恰为某值的股票对"。
8. 证明插入排序的运行时间为 \(\Theta(n+I)\)，\(I\) 为逆序对数；并设计 \(\Theta(n\lg n)\) 的逆序对计数算法。 提示：第 6 行每执行一次，恰好消除一个逆序对。
9. 思考题 2-1：在归并排序中对长度为 \(k\) 的子表改用插入排序，证明总时间为 \(\Theta(nk+n\lg(n/k))\)，并说明 \(k\) 最大可取多少。然后用 Python 实测你机器上的合适 \(k\)。 答案：\(k=\Theta(\lg n)\)。
10. 为霍纳规则写出循环不变式并证明正确；比较它与逐项计算 \(a_kx^k\) 的运行时间。

原书推荐习题：1.2-2、1.2-3、思考题 1-1（体会增长率与常数因子）；1.1-4、1.1-5（区分精确最优与近似可接受的问题）；2.1-3（循环不变式格式）；2.3-5、2.3-7（二分查找、排序 + 双指针）；思考题 2-1（混合排序阈值）、2-3（霍纳规则）、2-4（逆序对，与 Kendall \(\tau\) 直接相关，强烈推荐）。

原书对照

原书 Part I 导言见 PDF p.23–25；第 1 章章末注记 p.36、第 2 章章末注记 p.63 给出了算法教材与排序历史的参考文献。