算法分析与设计 第2讲 —— 数学基础
课程：北京大学软件研究所 · 算法设计与分析（0A002） 讲师：屈婉玲 内容：第2讲 数学基础，49页
概述
本讲是算法分析的数学工具箱，覆盖五大模块：
- 符号与函数：取整函数、对数、阶乘
- 求和技术：基本求和公式、和式上界估计（放大法/积分法）
- 递推方程求解：公式法（特征根）、换元法、迭代归纳（差消）法、尝试法
- 递归树法：可视化迭代过程，逐层求和
- Master 定理：分治算法复杂度分析的”三招必杀技”
核心目标：为后续各讲的算法复杂度分析提供数学工具。
一、基础符号与函数
1.1 取整函数
- ⎣x⎦：小于等于 x 的最大整数（下取整）
- ⎡x⎤：大于等于 x 的最小整数（上取整）
重要性质：
- x - 1 < ⎣x⎦ ≤ x ≤ ⎡x⎤ < x + 1
- ⎡n/2⎤ + ⎣n/2⎦ = n （二分算法中频繁使用）
- ⎡⎡n/a⎤/b⎤ = ⎡n/(ab)⎤ （多层上取整可合并）
算法意义：二分、分治、递归划分规模时，取整决定了子问题规模。
1.2 对数
约定（算法领域）：
- log n = log₂ n （默认以 2 为底）
- lg n = log₂ n
- logᵏ n = (log n)ᵏ （k 次幂）
- log log n = log(log n) （对数的对数，增长极慢）
常用等式：
- 换底公式：log_b n = log₂ n / log₂ b
- a^{log_b n} = n^{log_b a} （指数与对数互换，Master 定理推导常用）
- log(n!) = Θ(n log n) （Stirling 近似，排序算法下界分析常用）
1.3 阶乘与 Stirling 公式
- n! = n × (n-1) × … × 1
- Stirling 近似：n! ≈ √(2πn) · (n/e)ⁿ
- log(n!) = Θ(n log n) （重要结论，比较排序的 Ω(n log n) 下界基于此）
二、求和技术
2.1 基本求和公式
| 公式 | 结果 | 适用场景 |
|---|---|---|
| ∑_{k=1}^n k | n(n+1)/2 | 双重循环、选择排序 |
| ∑_{k=1}^n k² | n(n+1)(2n+1)/6 | 某些三重循环 |
| ∑_{k=0}^n arᵏ | a(1-r^{n+1})/(1-r) | 几何级数，分治递归 |
| ∑_{k=0}^∞ arᵏ (r<1) | a/(1-r) | 收敛的无穷级数 |
| ∑_{k=1}^n 1/k | ln n + γ + o(1) | 调和级数，快速排序平均 |
2.2 估计和式的上界
方法一：放大法
最简单：∑ a_k ≤ n · a_max
更精细：如果 a_{k+1}/a_k ≤ r（r < 1，公比型衰减），则 ∑{k=0}^n a_k ≤ ∑{k=0}^∞ a₀ rᵏ = a₀ / (1 - r)
例：∑_{k=1}^n k/3ᵏ ，公比 = 2/3 < 1，上界 ≤ 1
方法二：积分法
对于单调递减函数 f(x)：
- ∫₁^{n+1} f(x)dx ≤ ∑_{k=1}^n f(k) ≤ f(1) + ∫₁ⁿ f(x)dx
对于单调递增函数 f(x)：
- ∫₀ⁿ f(x)dx ≤ ∑_{k=1}^n f(k) ≤ ∫₁^{n+1} f(x)dx
典型应用：∑{k=1}^n 1/k = Θ(log n)，∑{k=1}^n k log k = Θ(n² log n)
三、递推方程求解
3.1 递推方程定义
把 a_n 与某些个 a_i（i < n）联系起来的等式，给定初值唯一确定序列。
典型例子：
- Fibonacci：f_n = f_{n-1} + f_{n-2}, f₀ = f₁ = 1
- 阶乘：F(n) = n·F(n-1), F(1) = 1
- Hanoi 塔：T(n) = 2T(n-1) + 1, T(1) = 1
3.2 求解方法总览
- 公式法（特征根法）—— 线性常系数递推
- 换元法 —— 变量替换简化形式
- 迭代归纳法（差消法） —— 逐步展开化简
- 尝试法 —— 猜阶+验证
- 递归树法 —— 可视化迭代
- Master 定理 —— 分治递推三分类
3.3 公式法（特征根法）
齐次线性常系数递推
标准型：
H(n) - a₁H(n-1) - a₂H(n-2) - … - a_k H(n-k) = 0
H(0) = b₀, H(1) = b₁, … , H(k-1) = b_{k-1}
步骤：
- 写出特征方程：xᵏ - a₁x^{k-1} - … - a_k = 0
- 求出 k 个特征根
- 根据根的重数构造通解
- 代入初值确定系数
无重根：H(n) = c₁q₁ⁿ + c₂q₂ⁿ + … + c_k q_kⁿ
有重根：若 q 是 e 重根，则贡献 (c₁ + c₂n + … + c_e n^{e-1}) · qⁿ
例：Fibonacci 数列 特征方程 x² - x - 1 = 0，根 (1±√5)/2 f_n = (1/√5)·[(1+√5)/2]^{n+1} - (1/√5)·[(1-√5)/2]
非齐次线性常系数递推
形式：齐次方程右端 = f(n)
解 = 齐次通解 + 特解 H*(n)
特解形式表：
| f(n) 形式 | 特征根情况 | 特解形式 |
|---|---|---|
| t 次多项式 | 1 不是特征根 | t 次多项式 P₁nᵗ + … + P_{t+1} |
| t 次多项式 | 1 是 e 重特征根 | nᵉ · t 次多项式 |
| βⁿ · t 次多项式 | β 不是特征根 | βⁿ · t 次多项式 |
| βⁿ · t 次多项式 | β 是 e 重特征根 | βⁿ · nᵉ · t 次多项式 |
例：Hanoi 塔 T(n) = 2T(n-1) + 1 齐次通解：c·2ⁿ，特解：P（常数），代入得 P = -1 T(n) = c·2ⁿ - 1，T(1) = 1 → c = 1 → T(n) = 2ⁿ - 1
3.4 迭代归纳法（差消法）
核心思想：逐项展开递推式，直到出现已知的求和模式。
适用场景：递推式中包含求和号（快速排序平均复杂度分析）
典型步骤（快排平均复杂度）：
- 递推式：nT(n) = 2∑_{i=1}^{n-1} T(i) + n² - n
- 写出 n-1 版本的式子，两式相减消去求和号
- 得到 nT(n) = (n+1)T(n-1) + 2n - 2
- 两边除以 n(n+1)，构造新变量叠代
- 结果：T(n) = O(n log n)
3.5 换元法
核心思想：通过变量替换将陌生递推转化为已知类型。
典型例子：二分查找
- T(n) = T(n/2) + 1，T(1) = 1
- 令 n = 2ᵏ，H(k) = T(2ᵏ)
- H(k) = H(k-1) + 1，H(0) = 1
- 解得 H(k) = k + 1 = log n + 1
3.6 尝试法
核心思想：先猜阶，再代入验证阶的高低，逐步逼近。
策略：
- 如果右边阶更高 → 提高 T(n) 的阶
- 如果左边阶更高 → 降低 T(n) 的阶
- 两边阶一致 → 猜中
例：T(n) = (2/n)∑_{i=1}^{n-1} T(i) + n - 1
- 猜常数 → 右边高
- 猜线性 cn → 右边高
- 猜二次 cn² → 左边高
- 猜 cn log n → 阶匹配，c = 2ln2
四、递归树法
4.1 基本思想
将递推式 T(n) = aT(n/b) + f(n) 逐层展开为树：
- 根节点代价：f(n)
- 第 1 层：a 个节点，每个代价 f(n/b)
- 第 2 层：a² 个节点，每个代价 f(n/b²)
- …
- 叶子层：a^{log_b n} = n^{log_b a} 个节点，每个 Θ(1)
总代价 = 各层代价之和
4.2 典型例子
例 1：T(n) = 2T(n/2) + n²
- 第 0 层：n²
- 第 1 层：2 × (n/2)² = n²/2
- 第 2 层：4 × (n/4)² = n²/4
- 等比数列，公比 1/2
- 总和 ≈ 2n² → Θ(n²)
例 2：T(n) = T(n/3) + T(2n/3) + n
- 每层总和都是 n
- 树高由最长路径决定：log_{3/2} n
- 总和 → Θ(n log n)
经验法则：哪层代价最大，总复杂度就由哪层主导。
- 叶子层最大 → Case 1（叶节点主导）
- 各层相近 → Case 2（均匀分布）
- 根节点最大 → Case 3（根主导）
五、Master 定理
5.1 定理表述
设 a ≥ 1, b > 1 为常数，f(n) 为函数，递推式： T(n) = aT(n/b) + f(n)
则有三种情况：
| 情况 | 条件 | 结果 | 直觉 |
|---|---|---|---|
| Case 1 | f(n) = O(n^{log_b a - ε}), ε > 0 | T(n) = Θ(n^{log_b a}) | 叶子层主导，f 小到可以忽略 |
| Case 2 | f(n) = Θ(n^{log_b a}) | T(n) = Θ(n^{log_b a} · log n) | 各层均匀，每层贡献相同 |
| Case 3 | f(n) = Ω(n^{log_b a + ε}), ε > 0 且 af(n/b) ≤ cf(n), c < 1 | T(n) = Θ(f(n)) | 根节点主导，f 增长太快 |
5.2 三个标准例子
Case 1 例：T(n) = 9T(n/3) + n
- a = 9, b = 3, n^{log_3 9} = n²
- f(n) = n = O(n^{2-1}) → Case 1
- T(n) = Θ(n²)
Case 2 例：T(n) = T(2n/3) + 1
- a = 1, b = 3/2, n^{log_{3/2} 1} = n⁰ = 1
- f(n) = 1 = Θ(1) → Case 2
- T(n) = Θ(log n)
Case 3 例：T(n) = 3T(n/4) + n log n
- a = 3, b = 4, n^{log_4 3} ≈ n
- f(n) = n log n = Ω(n^{0.793 + ε})
- 验证正则条件：3·(n/4)·log(n/4) ≤ (3/4)n log n = cf(n), c = 3/4 < 1 ✓
- T(n) = Θ(n log n)
5.3 不能用 Master 定理的情况
Master 定理不是万能的，以下情况需用递归树或其他方法：
-
f(n) 介于 Case 1 和 Case 2 之间（多项式差距不够 ε）
- 例：T(n) = 2T(n/2) + n / log n
- f(n) 比 n 小，但不是多项式地小（没有 ε 差距）
-
f(n) 介于 Case 2 和 Case 3 之间
- 例：T(n) = 2T(n/2) + n log n
- 实际上属于扩展 Master 定理的 Case 2 变体
-
不满足正则条件（Case 3 的 af(n/b) ≤ cf(n)）
-
子问题规模不均匀（如 T(n) = T(n/3) + T(2n/3) + n）
- 需用递归树法
5.4 扩展 Master 定理（补充）
Case 2 的扩展：若 f(n) = Θ(n^{log_b a} · logᵏ n)，k ≥ 0 则 T(n) = Θ(n^{log_b a} · log^{k+1} n)
六、取整与递推方程
递推中出现 ⎣n/2⎦ 或 ⎡n/2⎤ 怎么办？
方法：先忽略取整（视 n 为 2 的幂），猜出解，再用数学归纳法证明对所有 n 成立。
例：T(n) = 2T(⎣n/2⎦) + n, T(1) = 1 先按 n = 2ᵏ 解：T(n) = n log n + n 再用归纳法证明对所有 n 都有 T(n) = O(n log n)
结论：对于好的递推式，取整不影响渐近阶，可以放心忽略。
关键结论速查
| 递推形式 | 复杂度 | 典型算法 |
|---|---|---|
| T(n) = T(n/2) + 1 | Θ(log n) | 二分查找 |
| T(n) = T(n-1) + 1 | Θ(n) | 线性查找 |
| T(n) = 2T(n/2) + n | Θ(n log n) | 归并排序、快速排序（平均） |
| T(n) = 2T(n/2) + 1 | Θ(n) | 树的遍历 |
| T(n) = T(n-1) + n | Θ(n²) | 插入排序（最坏） |
| T(n) = 2T(n-1) + 1 | Θ(2ⁿ) | Hanoi 塔 |
| T(n) = n·T(n-1) | Θ(n!) | 全排列生成 |
关联
- 算法分析与设计 第1讲 —— 引言：课程概览与问题实例
- 《算法导论》-Introduction to Algorithms-第3版-CLRS：Master 定理详细证明与更多例子
- 后续第 3-4 讲：分治策略（本讲工具的直接应用）