算法设计第 1 章：引论——五大特性与渐进记号，先把尺子造出来
这一章不写任何"能直接交作业"的算法，它只做一件事：把"什么算算法""怎么衡量好坏"这两把尺子造出来。很多人把引论当名词背诵，结果到第 3 章说不清状态数和填表规模的关系，到第 8 章分不清 O 与 Θ 的语气差别。学完这一章，应当能对任意一段代码给出复杂度上界与下界，并能判断一个递归式大致属于哪一类。
一、算法的定义与五大特性
算法是求解某一类问题的一组明确指令：对符合规范的输入，在有限时间内产生所要求的输出。教材把它拆成五个特性：
- 有穷性：执行有穷步后终止，且每一步都在有限时间内完成。这一条把算法与程序区分开——操作系统是程序，不是算法。
- 确定性：每条指令含义唯一，相同的输入必得相同的输出，不允许"视情况而定"。
- 可行性：每条指令都能由基本运算经过有限次执行实现，不能出现"求任意实数的精确平方根"这种原理上做不到的步骤。
- 输入：零个或多个。零输入常被误认为不合法，其实打印一个固定常量也是算法。
- 输出：一个或多个，没有输出的计算不叫算法。
第 7 章的概率算法看似违反确定性，其实随机源被当作输入的一部分（或视为一条确定的伪随机序列），算法本身仍是确定的映射。
二、伪代码与抽象数据类型
伪代码介于自然语言与程序设计语言之间：保留赋值、分支、循环、递归，丢掉类型声明、分号、内存管理等噪声。写伪代码有三条纪律——数组下标统一（本课程从 1 开始）、块用缩进而非花括号、前置条件写在注释里。
抽象数据类型（ADT）是一个数学模型加上定义在该模型上的一组操作。它的价值在于使用与实现分离：ADT 只规定操作"做什么"，不规定"怎么做"。栈是 ADT，顺序栈与链栈是两种实现；同一份算法伪代码可以跑在任一实现上，但复杂度由实现决定。
这一点在后面反复出现：第 2 章的二分搜索要求 O(1) 随机访问，所以只能建在数组上，建在链表上就退化成 O(n)；第 4 章 Dijkstra 用邻接矩阵是 O(n²)，换成邻接表加堆就变成 O((n+m) log n)。算法不变、存储结构一换、复杂度量级就变，这是本课程最容易被忽略的一条主线。
三、算法描述语言与递归描述
描述层次有三档：自然语言有歧义，程序设计语言有细节噪声，伪代码是折中。递归描述是伪代码里最需要专门练的一种，因为递归写法直接把数学归纳法的证明结构搬进了代码：归纳基础对应基例，归纳步骤对应递归体。
写递归只需回答两个问题：什么时候停（基例是否覆盖了所有退化情形）、每次递归的规模是否真的变小（否则死循环）。汉诺塔的递归式 T(n) = 2T(n−1) + 1，解得 T(n) = 2ⁿ − 1；这个指数下界不是算法没写好，而是移动次数本身就有 2ⁿ − 1 的下界，属于问题固有的难度，第 8 章的 NP 完全问题常拿它作类比。
四、渐进记号：五个符号不要混用
| 记号 | 含义 | 直观说法 |
|---|---|---|
| O(g) | 上界，存在 c、n₀ 使 f(n) ≤ c·g(n) | f 增长不快于 g |
| Ω(g) | 下界，f(n) ≥ c·g(n) | f 增长不慢于 g |
| Θ(g) | 紧确界，同时是上界和下界 | f 与 g 同阶 |
| o(g) | f(n)/g(n) → 0 | f 严格慢于 g |
| ω(g) | f(n)/g(n) → ∞ | f 严格快于 g |
最容易错的是把 O 当 Θ 用。n = O(n²) 是成立的陈述，所以"快排最坏 O(n²)"与"快排最坏 Θ(n²)"强度完全不同，后者才是精确结论。教材正文写 O 多数是宽松说法，考试要求精确时应写 Θ。
运算规则：O(f) + O(g) = O(max(f, g))，O(f)·O(g) = O(fg)，常数因子与低阶项可丢。对数底不影响阶（换底只差常数），指数底影响极大：2ⁿ 与 3ⁿ 不同阶。递归式的系统解法（主定理、递归树、代换法）在第 2 章展开。
五、时间与空间复杂度
时间复杂度统计基本操作的执行次数，写成输入规模 n 的函数，与机器速度无关；这也是它比"跑一遍计时"可靠的原因。空间复杂度只算辅助空间，输入本身不算，但递归的调用栈必须算进去。
常见量级：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。
几条快判经验：单层循环到 n 是 O(n)；两层嵌套且内层上界与 i 相关，多数是 O(n²)；每步把规模减半是 O(log n)；递归式 T(n) = 2T(n/2) + O(n) 是 O(n log n)；T(n) = 2T(n/2) + O(1) 是 O(n)。
渐进记号丢掉常数，但工程上常数可能差一个量级：同为 O(n log n)，归并排序要额外 O(n) 空间与来回拷贝，快排原地划分的常数更小、访存更友好，所以标准库普遍选快排而非归并。同阶不等于同速，选型还要看常数、空间与缓存行为。
另一条分界是多项式时间：O(n^k) 记为多项式，O(2ⁿ) 与 O(n!) 记为指数。第 8 章的 P 类就是"存在多项式时间算法"的问题类，这条界线之所以重要，是因为多项式对指数只是"能跑与不能跑"的差别，而任意两个多项式之间的差距远没有这么致命。
六、最坏、最好与平均情况
这三种情况描述的是同一算法在不同输入上的表现，不是三个不同算法。
顺序查找：最好 1 次比较，最坏 n 次，等概率平均 (n+1)/2 = Θ(n)。快速排序：最好与平均 O(n log n)，最坏 O(n²)。
工程上优先看最坏情况，因为它给的是保证；平均情况需要概率模型，模型错了结论就失真。"平均 O(n log n)"不等于"实际跑起来快"——如果输入恰好接近有序，快排会稳定地落在最坏一侧。这正是第 7 章舍伍德算法要主动打乱输入、把最坏情况概率化的动机。
易错点
- 把 O 当 Θ 用，写出"该算法复杂度为 O(n²)"却在需要精确结论时被扣分。
- 认为算法必须有输入。零输入合法，零输出不合法。
- 算空间复杂度时漏掉递归栈，导致把归并排序写成 O(1)。
- 用运行时间比较算法优劣，忽略了常数、语言与机器差异。
这一章在整门课里的位置
本章不依赖任何前置章节，但它的记号贯穿全部十章：第 2 章要用递归式求解分治的复杂度，第 3 章要用状态数与转移代价估算填表规模，第 8 章的 P 类定义就是"存在多项式时间算法的问题"。引论没吃透，后面每一章的复杂度都会写错。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 算法设计与分析（89讲） 89 讲