一、问题、实例与算法
一个计算问题（problem） 是输入集合到输出集合的一个关系：它规定了"对每个合法输入，什么样的输出算正确"。
排序问题 输入：n 个数的序列 ⟨a₁, a₂, …, aₙ⟩ 输出：该序列的一个重排 ⟨a′₁, a′₂, …, a′ₙ⟩，满足 a′₁ ≤ a′₂ ≤ … ≤ a′ₙ
注意这里的措辞极其克制。它没有说"用什么方法"，只说了"什么结果算对"。这是本课程反复出现的分离：
| 概念 | 含义 |
|---|---|
| 问题（problem） | 输入到输出的规范。不含方法。 |
| 实例（instance） | 一个具体输入，如 ⟨31, 41, 59, 26⟩ |
| 算法（algorithm） | 一个良定义的计算过程，把输入变成输出 |
一个算法称为对该问题正确（correct），当且仅当：对每一个合法实例，它都能停机，并输出满足规范的结果。
⚠️ 注意"每一个"。一个在 99% 输入上正确的过程不叫正确的算法，它叫启发式（heuristic）。启发式有它的位置（见第 34 讲），但不能混为一谈。
二、计算模型：RAM
说"这个算法要 n log n 时间"，前提是我们约定了什么算一步。没有模型，效率无从谈起。
本课程使用 RAM 模型（Random-Access Machine）：
（1）指令集：以下每条算作一步（常数时间）：
- 算术：
+ - × ÷ mod、下取整、上取整 - 数据移动：读内存、写内存、赋值
- 控制：条件跳转、无条件跳转、子程序调用与返回
- 比较
（2）内存：一个无限大的数组，任意下标的读写都是一步。这就是"随机访问"的含义——访问 A[0] 和访问 A[10⁶] 代价相同。
（3）字长（word size）：内存的每个单元存放 w 比特。标准假设是
w ≥ log₂ n
为什么必须有这个假设？ 因为我们需要一个下标能寻址整个输入。如果 w < log n，连"指向第 n 个元素的指针"都存不下，遍历数组都不是 O(n) 了。反过来，我们也不允许 w 任意大——否则可以把整个输入编码进一个整数，用几次算术运算解决所有问题，模型就失去意义。
模型是一种谎言，但是有用的谎言
RAM 模型明显不真实：
| RAM 假设 | 真实机器 |
|---|---|
| 所有内存访问代价相同 | L1 缓存 ~1ns，主存 ~100ns，SSD ~100μs |
| 乘法和加法都是一步 | 乘法慢几倍，除法慢十几倍 |
| 内存无限 | 会 OOM |
那为什么还用它？因为它在正确的粒度上区分算法。O(n²) 和 O(n log n) 的差距，在 n = 10⁶ 时是 5 万倍，任何常数因子和缓存效应都盖不住它。RAM 模型丢掉了常数，保留了量级——而量级正是设计决策的依据。
当常数真的开始主导时（数据放不进内存、或算法都在同一量级），我们会换模型。第 18 讲的 外存模型（External Memory Model） 就是这样一个例子：它只数磁盘块传输次数，把 CPU 计算当成免费的。
三、正确性：循环不变式
如何证明一个算法对所有输入都正确？穷举测试是不可能的。标准工具是循环不变式（loop invariant）——本质上是伪装成程序注释的数学归纳法。
以插入排序为例（详见第 9 讲）：
func InsertionSort(a []int) {
for j := 1; j < len(a); j++ {
key := a[j]
i := j - 1
for i >= 0 && a[i] > key {
a[i+1] = a[i]
i--
}
a[i+1] = key
}
}
循环不变式：在外层 for 每次迭代开始前，子切片 a[0:j] 由原来 a[0:j] 中的元素组成，且已排好序。
证明分三段，必须三段都写：
① 初始化（Initialization）——第一次迭代前不变式成立。
j = 1 时，a[0:1] 只有一个元素，就是原来的 a[0]，平凡有序。✓
② 保持（Maintenance）——若某次迭代前成立，则下次迭代前仍成立。
内层 for 把 a[j-1], a[j-2], … 中所有大于 key 的元素依次右移一位，直到找到 ≤ key 的位置，把 key 放进去。结果 a[0:j+1] 有序，且元素集合不变。j 加 1 后，不变式对新的 j 成立。✓
③ 终止（Termination）——循环结束时，不变式给出我们要的结论。
循环在 j = n 时结束。代入不变式：a[0:n] 由原元素组成且有序。这正是排序问题的规范。 ∎
⭐ 第三步是最容易被跳过、也最关键的一步。 一个不变式如果在终止时推不出目标结论，它再"真"也没用。选不变式的技巧就是倒着想：先写下终止时想要什么，再想在循环中途它的"部分版本"是什么样。
为什么这是归纳法
初始化 ≙ 归纳基础；保持 ≙ 归纳步骤。区别只在于：数学归纳会一直归纳到无穷，而循环不变式的归纳在循环终止时停下——多出来的第三步，正是处理这个"停下"的。
四、递归算法的正确性
递归算法用强归纳法证明。模板：
- 基础情形：对最小规模的输入，直接验证。
- 归纳假设：假设对所有规模 < n 的输入，递归调用都返回正确结果。
- 归纳步骤：在此假设下，证明当前这一层的组合逻辑给出正确结果。
关键心态转变：你不必在脑子里展开递归。 你只需要相信"更小的调用是对的"，然后检查这一层。展开递归去追踪调用栈，是初学者最常见也最耗时的错误习惯。
对应地，递归算法的时间分析用递归式（recurrence），见第 3 讲。
另外还要证明停机性：找一个随每次递归调用严格减小、且有下界的量（通常是输入规模）。这个量在程序验证里叫变界函数（variant）——不变式保证"对"，变界函数保证"停"。
五、抽象数据类型与数据结构
这是本课程 Unit 2 到 Unit 4 的组织主线，务必分清：
| 抽象数据类型（ADT） | 数据结构（Data Structure） | |
|---|---|---|
| 是什么 | 一组操作的规范：能做什么，语义是什么 | 一种实现：数据在内存里怎么摆 |
| 回答的问题 | What | How |
| 例子 | 优先队列：insert、extract-min |
二叉堆、配对堆、Fibonacci 堆 |
| 例子 | 有序字典：search、insert、predecessor |
红黑树、跳表、B 树 |
┌────────────────────────────────┐
│ ADT：优先队列 │ ← 接口 / 契约
│ insert(x) · extract-min() │
└───────────────┬────────────────┘
┌──────────┼──────────┐
▼ ▼ ▼
┌────────┐ ┌────────┐ ┌──────────┐
│ 有序数组│ │ 二叉堆 │ │ Fib 堆 │ ← 实现，各有取舍
│ ins O(n)│ │ O(log n)│ │ O(1)* │
│ ext O(1)│ │ O(log n)│ │ O(log n)*│
└────────┘ └────────┘ └──────────┘
* 摊还
为什么这个区分重要？ 因为选型问题永远是这样提出来的：
“我要一个能按优先级取最小、并且频繁下调优先级的结构。”
这句话确定了 ADT。剩下的工作是在实现之间比较各操作的代价，结合你的操作混合比例（workload mix） 做选择。如果 decrease-key 调用远多于 extract-min（Dijkstra 稠密图就是这样），Fibonacci 堆的 O(1) 摊还 decrease-key 才有意义；否则二叉堆的常数因子和缓存友好性会赢。
⭐ 一句话总结：ADT 决定你能不能解决问题，数据结构决定你解决得多快。
六、输入规模与运行情况
输入规模（input size） 的定义随问题而变，选错会导致复杂度结论错误：
| 问题 | 合理的规模度量 |
|---|---|
| 排序 | 元素个数 n |
| 图算法 | 顶点数 V 与边数 E（两个参数） |
| 大整数乘法 | 二进制位数，不是数值大小 |
| 矩阵乘法 | 阶数 n（输入实际有 n² 个数） |
⚠️ 一个经典陷阱：0-1 背包的 DP 是 O(nW)，看起来是多项式。但 W 是数值，它的编码长度是 log W。以输入长度计，这是 O(n·2^{log W})，是指数级——这叫伪多项式（pseudo-polynomial） 时间，见第 31 讲与第 34 讲。
三种运行情况：
- 最坏情况（worst case） T(n) = 规模 n 的所有输入中的最大代价。本课程的默认口径，因为它给出保证，且常常就是实际情况（数据库查不到的搜索总是走最坏路径）。
- 平均情况（average case）：需要假设输入分布，而这个假设常常不成立。
- 期望情况（expected case）：随机性来自算法自己（如随机化快排），与输入分布无关——所以比平均情况可靠得多。见第 11 讲。
随堂自测
- 为什么 RAM 模型要求字长 w ≥ log n？如果允许 w 任意大，会出什么问题？
- 循环不变式证明的三个步骤是什么？哪一步最常被遗漏，为什么它不可省略？
- 给下面的函数写出循环不变式，并完成三步证明：
func Sum(a []int) int { s := 0 for i := 0; i < len(a); i++ { s += a[i] } return s } - “优先队列"是 ADT 还是数据结构？“二叉堆"呢？用一句话说明二者的关系。
- 为什么说"平均情况分析"不如"期望运行时间"可靠？
- 一个算法在 n = 10⁶ 时跑得比另一个快，能否说明它渐近更优？反过来呢？