算法分析基础与学习路线

1. 概述与学习目标

1.1 什么是算法分析

算法分析（Algorithm Analysis）是研究算法所需资源（时间、空间、I/O、能量）与输入规模之间定量关系的学科。Donald E. Knuth 1968 在《The Art of Computer Programming, Volume 1: Fundamental Algorithms》第 1.2.10 节系统化算法分析为现代学科，并引入渐近记号的标准用法。算法分析的目标不是”算出运行时间的精确秒数”，而是回答以下四类核心问题：

1. 时间复杂度：算法在规模为 $n$ 的输入上需要多少基本操作？
2. 空间复杂度：算法需要多少额外存储？
3. 正确性：算法对所有合法输入是否产生正确输出？
4. 最优性：是否存在比该算法更优的算法？

算法分析层次模型：
                                算法分析
                                    |
        ┌───────────┬───────────────┴───────────────┬───────────┐
      时间分析    空间分析         正确性分析          最优性分析
        │            │                 │                  │
   ┌────┴────┐   ┌───┴───┐       ┌─────┴─────┐      ┌─────┴─────┐
  最坏  平均  最好  辅助   总空间    不变式    前后置    下界证明    上界证明
   摊还  期望  概率  空间             归纳法    条件     （Ω）      （O）

算法分析的五类渐近记号（Asymptotic Notation）：

1.2 算法与问题

算法（Algorithm）是一组有限的、明确定义的指令序列，用于解决某类问题或完成某项计算任务。一个有效的算法必须满足以下五个基本性质（Knuth 1968 TAOCP Vol.1 §1.1）：

判定问题（Decision Problem）：回答”是”或”否”。例如：给定图 $G$ 和整数 $k$，$G$ 中是否存在大小为 $k$ 的团？

优化问题（Optimization Problem）：在所有可行解中寻找最优解。例如：给定图 $G$，求最大团的大小。

两者之间存在深刻联系：优化问题通常可以转化为判定问题（通过二分答案），而判定问题的多项式时间算法往往能导出优化问题的算法。P vs NP 问题正是围绕判定问题的可解性展开的（Cook 1971, Karp 1972）。

1.3 问题规模与输入编码

问题规模 $n$ 是衡量输入大小的标尺，其选择直接影响复杂度函数的形式：

• 数组排序：$n$ = 数组长度
• 矩阵乘法：$n$ = 矩阵维度
• 图算法：$n$ 可以是顶点数 $|V|$ 或边数 $|E|$
• 整数运算：$n$ = 整数的二进制位数（注意：$n \neq$ 整数本身的值）

编码方式的选择也很关键。同一个整数，用一元编码（$n$ 个 1）和二进制编码（$\log n$ 位）表示，会导致完全不同的复杂度结论。在标准计算模型（图灵机/RAM）下，默认使用二进制编码。一元编码下的多项式时间算法，在二进制编码下变为伪多项式（pseudo-polynomial）时间，如 0-1 背包的 $O(nW)$ DP（$W$ 为背包容量，二进制编码下 $W$ 可达 $2^n$）。

跨模块引用：整数编码与位运算密切相关，参见 C++ 基础 中的位运算章节。

1.4 学习目标

完成本章学习后，读者应能够：

1. 记忆（Remember）：五类渐近记号的形式化定义、主定理三种情况、摊还分析三方法
2. 理解（Understand）：算法分析的历史脉络（Turing 1936 → Bachmann 1894 → Knuth 1976 → Hartmanis-Stearns 1965 → Cook 1971 → Karp 1972）
3. 应用（Apply）：使用主定理、代入法、递归树法求解递推关系，使用势能法分析数据结构摊还代价
4. 分析（Analyze）：归并/快速/堆/计数排序、Karatsuba/Strassen/FFT、二分查找、动态数组的复杂度证明
5. 评估（Evaluate）：各算法在时间/空间/稳定性/原地性/在线性/随机化维度上的优劣
6. 对比（Compare）：分治/贪心/动态规划/回溯/分支限界五大范式
7. 创造（Create）：设计基于算法分析的开源项目（可视化平台、复杂度分析工具、刷题追踪系统）

2. 历史动机与演进

2.1 计算理论的奠基（1930s）

Alan Turing 1936 在《On Computable Numbers, with an Application to the Entscheidungsproblem》（Proc. London Math. Soc. s2-42(1):230-265, DOI:10.1112/plms/s2-42.1.230）中提出图灵机（Turing Machine）作为通用计算模型，并证明停机问题不可判定。该论文解决了 Hilbert 1928 提出的”判定问题”（Entscheidungsproblem）：是否存在算法判定任意一阶逻辑公式是否可证——Turing 给出否定回答。Church 1936 同时用 λ-演算独立得到相同结论，故称 Church-Turing 论题：任何”有效计算”均可由图灵机完成。

图灵机定义（简化版）：

$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$

其中 $Q$ 为状态集，$\Sigma$ 为输入字母表，$\Gamma$ 为带字母表（$\Sigma \subseteq \Gamma$），$\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ 为转移函数，$q_0$ 为初始状态。

2.2 渐近记号的起源（1894-1976）

渐近记号的历史横跨数论到计算机科学：

Knuth 1976 论文的关键贡献：

1. 澄清 $O$ vs $\Theta$ 的区别：程序员误用 $O$ 表示”紧界”（实际应为 $\Theta$）
2. 推广 $\Omega$ 与 $\Theta$：使三者构成完整的上/下/紧界体系
3. 建议读法：$O$ 读作 “big-Omicron”（大 Omicron），$\Omega$ 读作 “big-Omega”，$\Theta$ 读作 “big-Theta”
4. 形式化定义：与 Bachmann-Landau 一致，强调 $O$ 是函数集合而非函数关系

2.3 计算复杂性理论的诞生（1960s）

Hartmanis-Stearns 1965 在《On the Computational Complexity of Algorithms》（Trans. AMS 117:285-306, DOI:10.1090/S0002-9947-1965-0170805-7）中系统化定义计算复杂性理论。关键贡献：

1. 多带图灵机模型：作为复杂度分析的统一模型
2. 时间复杂性类：$\text{TIME}(f(n))$ = 可在 $O(f(n))$ 时间内被图灵机求解的判定问题集合
3. 时间层次定理：$\text{TIME}(f(n)) \subsetneq \text{TIME}(f(n) \log f(n))$
4. 复杂性类的相对性：递归函数按时间复杂度形成严格层级

两人因此获 1993 年 Turing Award。

Cobham 1964 在《The intrinsic computational difficulty of functions》中独立定义 P 类（多项式时间）。Edmonds 1965 在《Paths, trees, and flowers》（Canad. J. Math. 17:449-467, DOI:10.4153/CJM-1965-045-4）中称多项式时间算法为”好算法”（good algorithm）。Cobham-Edmonds 论题：P 类是”易解”（tractable）问题的形式化。

2.4 NP 完全性的发现（1971-1972）

Cook 1971 在 STOC《The Complexity of Theorem-Proving Procedures》（pp. 151-158, DOI:10.1145/800157.805047）中证明 SAT 是 NP 完全的（Cook-Levin 定理，Levin 1973 独立证明）。这意味着：

• SAT ∈ NP
• ∀ $L \in \text{NP}$, $L \leq_p \text{SAT}$（多项式时间归约）

Cook 因此获 1982 年 Turing Award。

Karp 1972 在《Reducibility Among Combinatorial Problems》（Proc. IBM Symposium on Complexity of Computer Computations, pp. 85-103）证明 21 个经典组合问题均为 NP 完全，包括：

• 3-SAT
• 顶点覆盖（Vertex Cover）
• 团（Clique）
• 集合覆盖（Set Cover）
• 哈密尔顿回路（Hamiltonian Cycle）
• TSP 判定
• 子集和（Subset Sum）
• 背包判定
• 图着色（Graph Coloring）
• 3-维匹配（3-Dimensional Matching）

Karp 因此获 1985 年 Turing Award。P vs NP 千禧年七大难题之首（Clay Mathematics Institute Millennium Prize Problems, 2000），悬赏 100 万美元。

2.5 算法设计范式的发展

2.6 摊还分析的兴起（1980s）

Sleator-Tarjan 1985 在《Amortized Efficiency of List Update and Paging Rules》（CACM 28(2):202-208, DOI:10.1145/2786.2793）中系统化摊还分析（Amortored Analysis）：

1. 聚合分析（Aggregate Method）：求 $n$ 个操作总代价 $T(n)$，摊还代价 $= T(n)/n$
2. 核算方法（Accounting Method）：为不同操作赋予不同”摊还代价”，多余的存为”信用”
3. 势能方法（Potential Method）：定义势能函数 $\Phi(D)$，摊还代价 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$

Tarjan 1985 在《Amortized computational complexity》（SIAM J. Alg. Disc. Meth. 6(2):306-318, DOI:10.1137/0606031）进一步系统化，应用于 Splay 树（Sleator-Tarjan 1985）、并查集（Tarjan 1975）、二项堆等。Sleator-Tarjan 因此获 1986 年 Turing Award。

2.7 主定理的形式化（1980）

Bentley-Haken-Saxe 1980 在《A general method for solving divide-and-conquer recurrences》（SIGACT News 12(3):36-44, DOI:10.1145/1008861.1008865）中系统化求解 $T(n) = aT(n/b) + f(n)$ 形式递推。该论文将递归树方法形式化，给出三种情况分类（基于 $f(n)$ 与 $n^{\log_b a}$ 的渐近比较）。Cormen-Leiserson-Rivest《CLRS》第 4 章将其命名为 Master Theorem（主定理）。

2.8 教材的奠基（1968-1990）

• Knuth 1968 《TAOCP Vol.1 Fundamental Algorithms》：算法分析的开山之作
• Aho-Hopcroft-Ullman 1974 《The Design and Analysis of Computer Algorithms》：Addison-Wesley，引入算法分析的标准教学体系
• Cormen-Leiserson-Rivest 1990 《Introduction to Algorithms》第 1 版（CLRS 第 1 版，2009 第 3 版加入 Stein，2022 第 4 版）：MIT 6.006 课程教材，全球最广泛使用的算法教材
• Sedgewick 1983 《Algorithms》第 1 版（2011 第 4 版与 Wayne 合著）：Princeton 课程教材，以图示与代码见长
• Kleinberg-Tardos 2006 《Algorithm Design》：Cornell 课程教材，以算法设计范式见长
• Skiena 1998 《The Algorithm Design Manual》第 1 版（2020 第 3 版）：Stony Brook 课程教材，以实战与”算法设计手册”风格见长

2.9 关键人物与里程碑

timeline
    title 算法分析关键里程碑
    1894 : Bachmann 大 O 符号
    1909 : Landau 推广渐近记号
    1936 : Turing 图灵机 / Church λ-演算
    1945 : von Neumann 归并排序
    1952 : Bellman 动态规划
    1960 : Land-Doig 分支限界
    1964 : Cobham P 类定义
    1965 : Hartmanis-Stearns 复杂性理论 / Edmonds P 类 / Golomb-Baumert 回溯
    1968 : Knuth TAOCP Vol.1 算法分析系统化
    1971 : Cook-Levin 定理 SAT NP 完全
    1972 : Karp 21 个 NP 完全问题 / Tarjan DFS 线性时间
    1976 : Knuth 渐近记号系统化 / Rabin 随机化算法
    1980 : Bentley-Haken-Saxe 主定理
    1985 : Sleator-Tarjan 摊还分析
    1990 : CLRS 第 1 版
    2000 : P vs NP 列入千禧年难题
    2022 : CLRS 第 4 版

2.10 关键设计决策

1. 图灵机作为统一计算模型（Turing 1936）：使复杂度分析独立于具体硬件
2. 二进制编码默认：使整数复杂度反映输入位数而非数值
3. 渐近记号而非精确常数：忽略硬件相关常数因子，聚焦算法本质
4. 最坏情况分析为主：保证算法对所有输入成立
5. 多项式时间作为”易解”判据（Cobham-Edmonds）：P 类的哲学基础
6. 摊还分析作为补充（Sleator-Tarjan 1985）：对数据结构操作序列给出更紧的界

3. 形式化定义

3.1 五类渐近记号的形式化定义

定义 3.1（大 O 符号）：设 $f, g: \mathbb{N} \to \mathbb{R}_{\geq 0}$，称 $f(n) = O(g(n))$ 当且仅当

$\exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0: 0 \leq f(n) \leq c \cdot g(n)$

含义：$f(n)$ 的增长率不超过 $g(n)$ 的常数倍，表示算法的最坏情况上界。

定义 3.2（大 Omega 符号）：称 $f(n) = \Omega(g(n))$ 当且仅当

$\exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0: 0 \leq c \cdot g(n) \leq f(n)$

含义：$f(n)$ 的增长率至少为 $g(n)$ 的常数倍，表示问题的固有难度下界。

定义 3.3（大 Theta 符号）：称 $f(n) = \Theta(g(n))$ 当且仅当

$f(n) = O(g(n)) \text{ 且 } f(n) = \Omega(g(n))$

即 $\exists c_1, c_2 > 0, \exists n_0, \forall n \geq n_0: c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$

含义：$f(n)$ 与 $g(n)$ 同阶增长，是最精确的复杂度描述。

定义 3.4（小 o 符号）：称 $f(n) = o(g(n))$ 当且仅当

$\forall c > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0: 0 \leq f(n) < c \cdot g(n)$

等价定义：$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$。

含义：$f(n)$ 的增长率严格小于 $g(n)$。例如 $n = o(n \log n)$。

定义 3.5（小 omega 符号）：称 $f(n) = \omega(g(n))$ 当且仅当

$\forall c > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0: 0 \leq c \cdot g(n) < f(n)$

等价定义：$\lim_{n \to \infty} \frac{f(n)}{g(n)} = +\infty$。

含义：$f(n)$ 的增长率严格大于 $g(n)$。例如 $n \log n = \omega(n)$。

3.2 渐近记号的运算性质

定理 3.1（渐近记号的运算性质）：

1. 传递性：若 $f = O(g)$ 且 $g = O(h)$，则 $f = O(h)$
2. 自反性：$f = O(f)$
3. 对称性：$f = \Theta(g)$ 当且仅当 $g = \Theta(f)$
4. 转置对称性：$f = O(g)$ 当且仅当 $g = \Omega(f)$
5. 加法规则：$O(f) + O(g) = O(\max(f, g))$
6. 乘法规则：$O(f) \cdot O(g) = O(f \cdot g)$

证明（加法规则）：设 $f_1 = O(g_1), f_2 = O(g_2)$，则 $\exists c_1, c_2, n_1, n_2$：

$\forall n \geq n_1: f_1(n) \leq c_1 g_1(n), \quad \forall n \geq n_2: f_2(n) \leq c_2 g_2(n)$

取 $n_0 = \max(n_1, n_2), c = c_1 + c_2$，则 $\forall n \geq n_0$：

$f_1(n) + f_2(n) \leq c_1 g_1(n) + c_2 g_2(n) \leq c \cdot \max(g_1(n), g_2(n))$

故 $f_1 + f_2 = O(\max(g_1, g_2))$。$\blacksquare$

3.3 常见复杂度等级

从快到慢排列（增长率单调递增）：

$O(1) \prec O(\log \log n) \prec O(\log n) \prec O(\sqrt{n}) \prec O(n) \prec O(n \log n) \prec O(n^2) \prec O(n^3) \prec O(2^n) \prec O(n!) \prec O(n^n)$

实际意义：假设每秒执行 $10^9$ 次运算：

3.4 计算模型

图灵机（Turing Machine, Turing 1936）：

$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$

• $Q$：有限状态集
• $\Sigma$：输入字母表（不含空白符 $\sqcup$）
• $\Gamma$：带字母表（$\Sigma \cup \{\sqcup\} \subseteq \Gamma$）
• $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$：转移函数
• $q_0 \in Q$：初始状态
• $q_{\text{accept}}, q_{\text{reject}} \in Q$：接受/拒绝状态

RAM 模型（Random Access Machine）：算法分析的事实标准模型，假设：

1. 每条基本指令（算术、比较、赋值、跳转、内存访问）耗时 $O(1)$
2. 内存无限大且随机访问
3. 每个字（word）可存储 $O(\log n)$ 位整数（$n$ 为输入规模）

Church-Turing 论题：任何”有效计算”均可被图灵机模拟。Cobham-Edmonds 论题：任何”易解”问题均可被多项式时间图灵机求解。

3.5 复杂性类的形式化定义

定义 3.6（P 类）：

$\text{P} = \bigcup_{k=1}^{\infty} \text{TIME}(n^k)$

即所有可在多项式时间内被确定图灵机求解的判定问题集合。

定义 3.7（NP 类）：

$\text{NP} = \bigcup_{k=1}^{\infty} \text{NTIME}(n^k)$

即所有可在多项式时间内被非确定图灵机求解的判定问题集合。等价定义：存在多项式 $p$ 与多项式时间验证器 $V$，使得

$x \in L \iff \exists w, |w| \leq p(|x|), V(x, w) = 1$

定义 3.8（NP 完全）：$L$ 是 NP 完全的当且仅当

1. $L \in \text{NP}$
2. $\forall L' \in \text{NP}: L' \leq_p L$（多项式时间归约）

定义 3.9（EXP 类）：

$\text{EXP} = \bigcup_{k=1}^{\infty} \text{TIME}(2^{n^k})$

已知包含关系：

$\text{P} \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXP}$

由时间层次定理（Hartmanis-Stearns 1965），$\text{P} \subsetneq \text{EXP}$。但 $\text{P}$ vs $\text{NP}$ 仍为开放问题。

3.6 递推关系的形式化定义

定义 3.10（递推关系）：形如

$T(n) = a \cdot T(n/b) + f(n), \quad a \geq 1, b > 1$

的递推关系，称为分治递推。其中 $a$ 为子问题数，$n/b$ 为子问题规模，$f(n)$ 为分解与合并代价。

主定理（Master Theorem, Bentley-Haken-Saxe 1980）：

对于 $T(n) = aT(n/b) + f(n)$，记 $n^{\log_b a}$ 为”叶子工作量”。设 $f(n)$ 渐近正，则：

情形 1：若 $f(n) = O(n^{\log_b a - \epsilon})$（对某个 $\epsilon > 0$），则 $T(n) = \Theta(n^{\log_b a})$

直觉：叶子节点总工作量支配根节点工作量。

情形 2：若 $f(n) = \Theta(n^{\log_b a} \log^k n)$（$k \geq 0$），则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$

直觉：各层工作量大致相等。

情形 3：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$（对某个 $\epsilon > 0$），且正则条件 $a \cdot f(n/b) \leq c \cdot f(n)$（对某个 $c < 1$ 与足够大的 $n$），则 $T(n) = \Theta(f(n))$

直觉：根节点工作量支配叶子节点总工作量。

4. 时空权衡

4.1 核心思想

算法设计中，时间与空间往往此消彼长。不存在同时达到时间最优和空间最优的”免费午餐”。时空权衡的核心策略有两类：

以空间换时间：使用额外的存储空间来加速计算。这是更常见的策略，因为内存成本持续下降而时间效率始终是核心瓶颈。

以时间换空间：在存储资源受限时，通过重复计算来减少存储需求。典型于嵌入式系统和大规模数据处理。

4.2 经典权衡案例

案例 1：排序中的辅助数组

归并排序需要 $O(n)$ 额外空间来实现合并操作，但保证了 $O(n \log n)$ 的时间复杂度。而原地排序（如堆排序）虽然空间为 $O(1)$，但常数因子更大且不稳定。

案例 2：搜索中的索引/哈希表

线性搜索 $O(n)$ 无需额外空间；构建哈希索引后查找降至 $O(1)$ 平均，但需要 $O(n)$ 额外空间。这是典型的空间换时间。

案例 3：动态规划中的备忘录

递归解法（如斐波那契）时间 $O(2^n)$ 空间 $O(n)$；加备忘录后时间 $O(n)$ 空间 $O(n)$；自底向上迭代后时间 $O(n)$ 空间可优化至 $O(1)$。

案例 4：布隆过滤器

用 $m$ 位比特数组近似表示 $n$ 个元素的集合，查询 $O(k)$（$k$ 个哈希函数），空间仅 $m/n$ 比特/元素，代价是存在假阳性（误判存在）。

案例 5：LRU 缓存

LRU 缓存用 $O(n)$ 额外空间（哈希表 + 双向链表）将缓存查询从 $O(n)$（线性扫描）降至 $O(1)$，是空间换时间的经典案例。

4.3 权衡决策框架

是否需要最优时间？ --是--> 空间是否充裕？ --是--> 以空间换时间
  |                    |
  |                    +--否--> 寻找时间-空间折中方案
  |
  +--否--> 空间是否受限？ --是--> 以时间换空间
           |
           +--否--> 平衡方案（如缓存策略）

量化分析：设 $S(n)$ 为空间开销，$T(n)$ 为时间开销。定义效率函数 $E(n) = T(n) \cdot S(n)^a$，其中 $a$ 为空间权重（$0 < a \leq 1$）。选择使 $E(n)$ 最小的方案。

4.4 工业级权衡决策表

5. 递推与主定理

5.1 递归树方法

递归树是分析分治算法的直观工具。将递推式 $T(n) = aT(n/b) + f(n)$ 展开为树形结构：

• 根节点的工作量为 $f(n)$
• 每个节点产生 $a$ 个子节点，每个子节点规模为 $n/b$
• 第 $i$ 层有 $a^i$ 个节点，每个节点工作量为 $f(n/b^i)$
• 树的深度为 $\log_b n$
• 总工作量 = 各层工作量之和

可视化：$T(n) = 2T(n/2) + cn$ 的递归树

                cn              第 0 层: cn
               /  \
             /    \
          cn/2    cn/2          第 1 层: cn
          / \     / \
        cn/4 cn/4 cn/4 cn/4     第 2 层: cn
        ... ... ... ...
        c  c  c  c  c  c        第 log n 层: cn
        总计: cn × (log n + 1) = O(n log n)

5.2 主定理（Master Theorem）

对于递推式 $T(n) = aT(n/b) + f(n)$，其中 $a \geq 1, b > 1$：

情形 1：若 $f(n) = O(n^{\log_b a - \epsilon})$（对某个 $\epsilon > 0$），则 $T(n) = \Theta(n^{\log_b a})$

直觉：叶子节点的总工作量支配根节点的工作量。

情形 2：若 $f(n) = \Theta(n^{\log_b a} \log^k n)$（$k \geq 0$），则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$

特殊情况 $k = 0$：若 $f(n) = \Theta(n^{\log_b a})$，则 $T(n) = \Theta(n^{\log_b a} \log n)$。

直觉：各层工作量大致相等。

情形 3：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$（对某个 $\epsilon > 0$），且正则条件 $a \cdot f(n/b) \leq c \cdot f(n)$（对某个 $c < 1$ 和足够大的 $n$），则 $T(n) = \Theta(f(n))$

直觉：根节点的工作量支配叶子节点的总工作量。

5.3 主定理应用示例

5.4 主定理的证明思路

证明（情形 2，$k = 0$，即 $f(n) = \Theta(n^{\log_b a})$）：

设 $f(n) = \Theta(n^{\log_b a})$，即 $\exists c_1, c_2 > 0$，对足够大 $n$ 有 $c_1 n^{\log_b a} \leq f(n) \leq c_2 n^{\log_b a}$。

递归树第 $i$ 层（$0 \leq i \leq \log_b n$）：

• 节点数：$a^i$
• 每节点工作量：$f(n/b^i) = \Theta((n/b^i)^{\log_b a}) = \Theta(n^{\log_b a} / a^i)$
• 第 $i$ 层总工作量：$a^i \cdot \Theta(n^{\log_b a} / a^i) = \Theta(n^{\log_b a})$

总工作量：

$T(n) = \sum_{i=0}^{\log_b n} \Theta(n^{\log_b a}) = \Theta(n^{\log_b a}) \cdot (\log_b n + 1) = \Theta(n^{\log_b a} \log n)$

$\blacksquare$

5.5 代入法

代入法（Substitution Method）是更通用的递推求解方法，步骤：

1. 猜测：根据递推式猜测 $T(n) = O(f(n))$
2. 归纳：假设 $T(k) \leq c \cdot f(k)$ 对所有 $k < n$ 成立
3. 验证：证明 $T(n) \leq c \cdot f(n)$

示例：$T(n) = 2T(n/2) + n$

猜测 $T(n) = O(n \log n)$。假设 $T(k) \leq c \cdot k \log k$ 对所有 $k < n$ 成立。则

$T(n) = 2T(n/2) + n \leq 2c \cdot (n/2) \log(n/2) + n = c n (\log n - 1) + n = c n \log n + (1 - c) n$

当 $c \geq 1$ 时，$T(n) \leq c n \log n$。$\blacksquare$

5.6 Akra-Bazzi 方法

Akra-Bazzi 1998 方法适用于更一般的递推形式：

$T(x) = \sum_{i=1}^{k} a_i T(b_i x + h_i(x)) + g(x)$

求解步骤：

1. 找 $p$ 满足 $\sum_{i=1}^{k} a_i b_i^p = 1$
2. 解为 $T(x) = \Theta\left(x^p \left(1 + \int_1^x \frac{g(u)}{u^{p+1}} du\right)\right)$

示例：$T(n) = 2T(n/2) + \frac{n}{\log n}$

$p = 1$ 满足 $2 \cdot (1/2)^1 = 1$。则

$T(n) = \Theta\left(n \left(1 + \int_1^n \frac{u/\log u}{u^2} du\right)\right) = \Theta\left(n \left(1 + \int_1^n \frac{du}{u \log u}\right)\right) = \Theta(n \log \log n)$

5.7 Python 实现：递归树可视化

import math
from typing import Callable

def analyze_recurrence(a: int, b: int, f_n: Callable[[float], float], n: int) -> tuple[list[float], float]:
    """
    分析递推式 T(n) = aT(n/b) + f(n) 的各层工作量。
    
    参数:
        a: 子问题数
        b: 子问题规模缩减因子
        f_n: 合并代价函数
        n: 输入规模
    
    返回:
        (各层工作量列表, 总工作量)
    """
    log_b_a = math.log(a, b)
    levels = int(math.log(n, b))
    work_per_level = []
    for i in range(levels + 1):
        num_nodes = a ** i
        work_per_node = f_n(n / (b ** i))
        level_work = num_nodes * work_per_node
        work_per_level.append(level_work)
    total = sum(work_per_level)
    return work_per_level, total

# 归并排序递推: T(n) = 2T(n/2) + n
def f_merge_sort(n: float) -> float:
    return n

work, total = analyze_recurrence(2, 2, f_merge_sort, 1024)
for i, w in enumerate(work):
    print(f"Level {i}: {w:.1f}")
print(f"Total: {total:.1f}")
# Level 0: 1024.0
# Level 1: 1024.0
# ...
# Level 10: 1024.0
# Total: 11264.0 ≈ 1024 * 11 = 1024 * (log2(1024) + 1)

5.8 C++ 实现：主定理判定

#include <iostream>
#include <vector>
#include <cmath>
#include <functional>
#include <string>
#include <iomanip>
using namespace std;

// 主定理判定器
struct MasterTheoremResult {
    int case_num;          // 情形 1/2/3
    string solution;       // 渐近解
    string explanation;    // 解释
};

MasterTheoremResult applyMasterTheorem(int a, int b, const string& f_n_desc, double log_b_a, double f_exponent) {
    // f_exponent: f(n) 的渐近指数（如 f(n)=n^2 -> 2; f(n)=n -> 1; f(n)=1 -> 0）
    // log_b_a: log_b(a)
    cout << fixed << setprecision(4);
    cout << "a=" << a << ", b=" << b << ", log_b(a)=" << log_b_a << ", f(n) ~ n^" << f_exponent << endl;
    
    if (f_exponent < log_b_a - 1e-9) {
        return {1, "Theta(n^" + to_string(log_b_a) + ")", "情形1: 叶子工作量支配"};
    } else if (abs(f_exponent - log_b_a) < 1e-9) {
        return {2, "Theta(n^" + to_string(log_b_a) + " * log n)", "情形2: 各层工作量相等"};
    } else if (f_exponent > log_b_a + 1e-9) {
        return {3, "Theta(f(n))", "情形3: 根节点工作量支配"};
    }
    return {0, "主定理不适用", "需用代入法或 Akra-Bazzi"};
}

int main() {
    // 归并排序: T(n) = 2T(n/2) + n
    auto r1 = applyMasterTheorem(2, 2, "n", log(2)/log(2), 1.0);
    cout << "归并排序: " << r1.solution << " (" << r1.explanation << ")" << endl;
    
    // Strassen: T(n) = 7T(n/2) + n^2
    auto r2 = applyMasterTheorem(7, 2, "n^2", log(7)/log(2), 2.0);
    cout << "Strassen: " << r2.solution << " (" << r2.explanation << ")" << endl;
    
    // Karatsuba: T(n) = 3T(n/2) + n
    auto r3 = applyMasterTheorem(3, 2, "n", log(3)/log(2), 1.0);
    cout << "Karatsuba: " << r3.solution << " (" << r3.explanation << ")" << endl;
    
    return 0;
}

5.9 Java 实现：复杂度计算器

import java.util.function.Function;

public class ComplexityAnalyzer {
    
    /**
     * 主定理判定器。
     * @param a 子问题数
     * @param b 子问题规模缩减因子
     * @param fExponent f(n) 的渐近指数
     * @return 渐近解字符串
     */
    public static String masterTheorem(int a, int b, double fExponent) {
        double logBA = Math.log(a) / Math.log(b);
        final double EPS = 1e-9;
        
        if (fExponent < logBA - EPS) {
            return String.format("情形1: Theta(n^%.4f) (叶子支配)", logBA);
        } else if (Math.abs(fExponent - logBA) < EPS) {
            return String.format("情形2: Theta(n^%.4f * log n) (各层相等)", logBA);
        } else {
            return String.format("情形3: Theta(f(n)) = Theta(n^%.4f) (根支配)", fExponent);
        }
    }
    
    /**
     * 递归树分析。
     */
    public static double[] recursionTree(int a, int b, Function<Double, Double> f, int n) {
        int levels = (int) (Math.log(n) / Math.log(b));
        double[] workPerLevel = new double[levels + 1];
        for (int i = 0; i <= levels; i++) {
            double numNodes = Math.pow(a, i);
            double workPerNode = f.apply(n / Math.pow(b, i));
            workPerLevel[i] = numNodes * workPerNode;
        }
        return workPerLevel;
    }
    
    public static void main(String[] args) {
        // 归并排序
        System.out.println("归并排序: " + masterTheorem(2, 2, 1.0));
        // Strassen
        System.out.println("Strassen: " + masterTheorem(7, 2, 2.0));
        // Karatsuba
        System.out.println("Karatsuba: " + masterTheorem(3, 2, 1.0));
        // 二分查找
        System.out.println("二分查找: " + masterTheorem(1, 2, 0.0));
    }
}

6. 摊还分析

6.1 为什么需要摊还分析

最坏情况分析有时过于悲观。某些数据结构的大部分操作代价很低，偶尔出现一次高代价操作。摊还分析（Amortized Analysis，Sleator-Tarjan 1985）关注 $n$ 个操作的序列总代价，而非单个操作的最坏代价，从而给出更紧的界。

关键区别：

• 平均情况分析：依赖概率假设（如随机化快速排序的 $O(n \log n)$ 期望）
• 摊还分析：不依赖概率，保证对任意操作序列成立

6.2 聚合分析（Aggregate Method）

对 $n$ 个操作的序列，计算总代价的上界 $T(n)$，则每个操作的摊还代价为 $T(n)/n$。

示例：动态数组扩容

动态数组（如 C++ vector、Python list、Java ArrayList）在容量满时扩容为原来的 2 倍：

class DynamicArray:
    """动态数组实现：容量满时倍增扩容。"""
    
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity
    
    def push_back(self, val: int) -> None:
        """向数组末尾添加元素，均摊 O(1)。"""
        if self.size == self.capacity:
            # 扩容：旧数据复制到新数组
            new_data = [None] * (self.capacity * 2)
            for i in range(self.size):
                new_data[i] = self.data[i]
            self.data = new_data
            self.capacity *= 2
        self.data[self.size] = val
        self.size += 1

分析 $n$ 次 push_back 的总代价：

• 普通插入：$O(1)$ 每次
• 扩容发生在第 $1, 2, 4, 8, \ldots, 2^k$ 次插入时
• 扩容代价：$1 + 2 + 4 + \ldots + n/2 < n$
• 总代价：$n$（普通插入）$+ n$（扩容）$= O(n)$
• 摊还代价：$O(n)/n = O(1)$

#include <vector>
#include <iostream>
using namespace std;

class DynamicArray {
    int* data;
    int cap, sz;
public:
    DynamicArray() : data(new int[1]), cap(1), sz(0) {}
    ~DynamicArray() { delete[] data; }
    
    // 均摊 O(1) 的 push_back
    void push_back(int val) {
        if (sz == cap) {
            int* newData = new int[cap * 2];
            for (int i = 0; i < sz; i++) newData[i] = data[i];
            delete[] data;
            data = newData;
            cap *= 2;
        }
        data[sz++] = val;
    }
    
    int operator[](int i) const { return data[i]; }
    int size() const { return sz; }
    int capacity() const { return cap; }
};

int main() {
    DynamicArray arr;
    for (int i = 0; i < 16; i++) {
        arr.push_back(i);
        cout << "size=" << arr.size() << ", cap=" << arr.capacity() << endl;
    }
    return 0;
}

6.3 核算法（Accounting Method）

为不同类型的操作赋予不同的摊还代价（“收费”），使得：

• 摊还代价 $\geq$ 实际代价时，多余部分作为”信用”存储在数据结构中
• 摊还代价 $<$ 实际代价时，用存储的信用来支付差额
• 信用始终非负

动态数组 push_back 的核算法分析：

• 普通插入：实际代价 1，摊还代价 3（1 用于插入，1 作为信用留给未来扩容时的复制，1 留给配对元素）
• 扩容插入：实际代价 $= 1$（插入）$+ sz$（复制），但 $sz$ 个元素的信用恰好支付复制代价
• 摊还代价 $= O(1)$

6.4 势能法（Potential Method）

Sleator-Tarjan 1985 系统化的势能法。定义势能函数 $\Phi(D)$ 将数据结构状态映射为非负实数。操作 $i$ 的摊还代价：

$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$

其中 $c_i$ 为实际代价。若 $\Phi(D_0) = 0$ 且对所有 $i$ 有 $\Phi(D_i) \geq 0$，则总摊还代价是总实际代价的上界。

动态数组的势能函数：$\Phi(D) = 2 \cdot \text{size} - \text{capacity}$

• 普通插入（未扩容）：$\hat{c}_i = 1 + (2(sz+1) - cap) - (2 sz - cap) = 1 + 2 = 3$
• 扩容插入（$cap$ 从 $k$ 变为 $2k$，$sz$ 从 $k$ 变为 $k+1$）：

$\hat{c}_i = (1 + k) + (2(k+1) - 2k) - (2k - k) = 1 + k + 2 - k = 3$

两种情况下摊还代价均为 3，即 $O(1)$。

6.5 多重弹栈示例

考虑一个栈支持三种操作：

• Push(S, x)：$O(1)$
• Pop(S)：$O(1)$
• Multipop(S, k)：弹出 $\min(k, |S|)$ 个元素，$O(\min(k, |S|))$

$n$ 个操作序列的聚合分析：

• 每个元素最多被 push 一次、pop 一次
• 总 pop 次数（包括 Multipop 中的）不超过总 push 次数
• 总代价 $\leq 2n = O(n)$
• 摊还代价 $= O(1)$

6.6 Splay 树的摊还分析

Sleator-Tarjan 1985 证明 Splay 树的所有操作（search/insert/delete）摊还 $O(\log n)$。势能函数：

$\Phi(T) = \sum_{x \in T} \log_2 |T_x|$

其中 $|T_x|$ 为以 $x$ 为根的子树大小，$\log |T_x|$ 称为节点 $x$ 的秩（rank）。

伸展操作（Splay）的摊还代价分析涉及 zig/zig-zig/zig-zag 三种情形，每种均能证明摊还代价 $\leq 3(\log |T| - \log |T_x|) + O(1)$，求和后摊还 $O(\log n)$。

6.7 三种方法对比

7. 算法设计范式总览

7.1 五大范式对比

7.2 分治 vs 贪心 vs 动态规划

分治（Divide and Conquer）的本质是”独立”：

• 将问题分解为互不重叠的子问题
• 分别求解后合并
• 子问题之间没有依赖关系
• 例子：归并排序中左半和右半独立排序

贪心（Greedy）的本质是”短视”：

• 在每一步做出局部最优选择
• 不回头、不撤销
• 依赖贪心选择性质：局部最优能导向全局最优
• 例子：Dijkstra 算法中每次选最近节点

动态规划（Dynamic Programming）的本质是”记忆”：

• 子问题重叠，需要避免重复计算
• 通过记录子问题的解来消除冗余
• 依赖最优子结构：最优解包含子问题的最优解
• 例子：Floyd-Warshall 中 $\text{dist}[k][i][j]$ 依赖 $\text{dist}[k-1]$ 层

决策流程：

问题是否可分解为独立子问题？ --是--> 分治
  |
  +--否--> 问题是否有最优子结构？ --否--> 回溯/暴力搜索
           |
           +--是--> 局部最优能否导向全局最优？ --是--> 贪心
                    |
                    +--否--> 子问题是否重叠？ --是--> 动态规划
                             |
                             +--否--> 分治（但可能需要更巧妙的分解）

7.3 范式选择的常见误区

1. 贪心与 DP 混淆：0-1 背包贪心不可行，但分数背包贪心可行。关键区别在于物品是否可分割——不可分割导致贪心选择的”不可逆”与全局最优矛盾。
2. 分治与 DP 混淆：分治的子问题不重叠，DP 的子问题重叠。如果分治递归中出现大量重复子问题，应考虑 DP。
3. 回溯与分支限界混淆：回溯用 DFS 搜索，分支限界用 BFS/最佳优先。回溯适合找一个解，分支限界适合找最优解。

跨模块引用：各范式的详细实现分别参见 排序算法（分治）、贪心算法、动态规划、递归与回溯。

8. 经典应用案例

8.1 案例一：归并排序复杂度分析

算法（von Neumann 1945）：

def merge_sort(arr: list[int]) -> list[int]:
    """归并排序：T(n) = 2T(n/2) + O(n) = O(n log n)。"""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a: list[int], b: list[int]) -> list[int]:
    """合并两个有序数组 O(n)。"""
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

复杂度分析：

递推关系：$T(n) = 2T(n/2) + O(n)$

由主定理情形 2（$a = 2, b = 2, \log_b a = 1, f(n) = n = \Theta(n^1)$）：

$T(n) = \Theta(n \log n)$

空间复杂度：$O(n)$（辅助数组）

8.2 案例二：快速排序期望分析

算法（Hoare 1961）：

import random

def quick_sort(arr: list[int]) -> list[int]:
    """随机化快速排序：期望 O(n log n)，最坏 O(n^2)。"""
    if len(arr) <= 1:
        return arr
    pivot_idx = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_idx]
    left = [x for i, x in enumerate(arr) if x <= pivot and i != pivot_idx]
    right = [x for i, x in enumerate(arr) if x > pivot and i != pivot_idx]
    return quick_sort(left) + [pivot] + quick_sort(right)

期望复杂度分析：

设 $T(n)$ 为期望时间。随机 pivot 等概率选取，子问题规模 $k$ 与 $n - 1 - k$（$0 \leq k \leq n-1$）：

$T(n) = \frac{1}{n} \sum_{k=0}^{n-1} [T(k) + T(n-1-k)] + O(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + O(n)$

用代入法证明 $T(n) = O(n \log n)$：假设 $T(k) \leq c k \log k$ 对所有 $k < n$ 成立。则

$T(n) \leq \frac{2c}{n} \sum_{k=1}^{n-1} k \log k + O(n) \leq \frac{2c}{n} \cdot \frac{n^2 \log n}{2} + O(n) = c n \log n + O(n)$

（用积分 $\int_1^n x \log x \, dx \leq \frac{n^2 \log n}{2}$）

故 $T(n) = O(n \log n)$。$\blacksquare$

8.3 案例三：二分查找

算法：

def binary_search(arr: list[int], target: int) -> int:
    """二分查找：T(n) = T(n/2) + O(1) = O(log n)。"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1