数学基础与算法分析 formalism

算法分析的形式化框架是计算机科学理论的核心基石，它为我们提供了一套严谨的语言来描述和比较算法的效率。本章将系统地回顾支撑算法分析所需的数学基础，包括离散数学、概率论、递归方程求解以及渐进分析理论。我们将深入探讨大O（Big O）、大Ω（Big Ω）、大Θ（Big Θ）表示法的严格定义，证明主定理（Master Theorem）及其扩展，并详细阐述摊还分析（amortized analysis）的三种经典方法：聚合（aggregate）、记账（accounting）和势能（potential）方法。通过形式化的语言和严密的逻辑，本章旨在建立一个无歧义的算法评估框架，为后续各章对具体数据结构和算法的深入分析奠定坚实的理论基础。

离散数学基础

离散数学为算法分析提供了基本的语言和工具，其核心概念如集合、关系、函数、图论以及数学归纳法贯穿于整个算法设计与分析过程。本节将回顾这些概念的形式化定义及其在算法上下文中的典型应用。

集合与关系

集合（set）是离散对象的总体，用大写字母表示，如 $S$。元素属于集合记为 $x \in S$，不属于记为 $x \notin S$。空集记为 $\emptyset$。集合的基数（cardinality）$|S|$ 表示元素个数。子集（subset）$A \subseteq B$ 当且仅当 $\forall x (x \in A \rightarrow x \in B)$。若 $A \subseteq B$ 且 $A \neq B$，则 $A$ 是真子集（proper subset），记为 $A \subset B$。

基本运算包括并集（union）$A \cup B = \{x \mid x \in A \lor x \in B\}$、交集（intersection）$A \cap B = \{x \mid x \in A \land x \in B\}$、差集（difference）$A \setminus B = \{x \mid x \in A \land x \notin B\}$，以及笛卡尔积（Cartesian product）$A \times B = \{(a,b) \mid a \in A, b \in B\}$。幂集（power set）$\mathcal{P}(S)$ 是 $S$ 所有子集的集合，其基数为 $2^{|S|}$。

在算法中，集合常用于表示状态空间、输入域或输出集合。例如，图的顶点集 $V$ 和边集 $E$ 是图论算法的基础。关系（relation）是笛卡尔积的子集。若 $R \subseteq A \times B$，则 $R$ 是从 $A$ 到 $B$ 的关系。若 $A=B$，则 $R$ 是 $A$ 上的关系。重要性质包括自反性（reflexive）、对称性（symmetric）、反对称性（antisymmetric）和传递性（transitive）。等价关系（equivalence relation）是自反、对称、传递的，它将集合划分为等价类（equivalence class）。偏序关系（partial order）是自反、反对称、传递的，记为 $\preceq$，其上的最小元素、最大元素、极大元素、极小元素等概念在贪心算法和动态规划中常见。例如，在拓扑排序中，有向无环图（DAG）的顶点间偏序关系决定了排序的可行性。

函数与映射

函数（function）$f: A \rightarrow B$ 是一种特殊的关系，满足每个 $a \in A$ 唯一对应 $b \in B$。$A$ 是定义域（domain），$B$ 是陪域（codomain），实际值域（range）是 $\{f(a) \mid a \in A\} \subseteq B$。函数是算法描述的核心：输入到输出的映射、状态转移函数、递归函数等。

关键概念包括单射（injective，一对一）、满射（surjective，映上）、双射（bijective，一一对应）。双射的存在意味着集合等势（equinumerous），在分析算法空间复杂度时，若输入空间与某种数据结构双射，则复杂度可转移。例如，排序算法中，输入排列与 $n!$ 个可能输出的双射关系是下界分析的基础。

组合数学中的排列（permutation）和组合（combination）是函数应用的特例。排列数 $P(n,k) = n!/(n-k)!$，组合数 $\binom{n}{k} = n!/(k!(n-k)!)$。这些计数在分析穷举搜索、回溯算法的时间复杂度时至关重要。例如，解决旅行商问题（TSP）的暴力算法需检查 $(n-1)!/2$ 条可能路径，其指数级增长揭示了问题的计算难度。

图论基础

图（graph）$G=(V,E)$ 由顶点集 $V$ 和边集 $E$ 组成。若边无方向，为无向图（undirected graph）；若有方向，为有向图（directed graph）。图的表示方法影响算法效率：邻接矩阵（adjacency matrix）需 $O(|V|^2)$ 空间，适合稠密图；邻接表（adjacency list）需 $O(|V|+|E|)$ 空间，适合稀疏图。在分析图算法（如BFS、DFS、最短路径）时，需明确以 $|V|$ 还是 $|E|$ 作为输入规模度量，通常 $|E| = O(|V|^2)$，故常用 $|V|$ 表示。

树（tree）是无环连通图。根树（rooted tree）有指定根节点，深度（depth）和高度（height）是递归定义的关键参数。二叉树（binary tree）每个节点最多两个子节点，高度 $h$ 的二叉树节点数最多 $2^{h+1}-1$。平衡二叉树（如AVL树、红黑树）通过保持高度 $O(\log n)$ 来保证操作对数时间。森林（forest）是无环图，等价于一组树。

图论中的基本算法如深度优先搜索（DFS）和广度优先搜索（BFS）的时间复杂度均为 $O(|V|+|E|)$，其正确性证明依赖于归纳法和不变式（invariant）维护。例如，DFS的递归调用栈深度最多 $|V|$，这决定了其空间复杂度。

逻辑与证明技术

数学归纳法（mathematical induction）是证明算法正确性和复杂度的核心工具。第一数学归纳法：若 $P(0)$ 真，且 $P(k) \rightarrow P(k+1)$ 对所有 $k \geq 0$ 成立，则 $P(n)$ 对所有 $n \in \mathbb{N}$ 成立。强归纳法（strong induction）：若 $P(0)$ 真，且 $P(0) \land P(1) \land \cdots \land P(k) \rightarrow P(k+1)$，则 $P(n)$ 对所有 $n$ 成立。在递归算法分析中，强归纳法常用于证明运行时间递归解的正确性。

循环不变式（loop invariant）是证明循环正确性的技术，需满足：初始化（循环前真）、保持（每次迭代后真）、终止（循环结束时推出所需性质）。例如，在插入排序中，循环不变式表述为“子数组 $A[1..i-1]$ 已排序”，其证明确保算法正确性。

反证法（proof by contradiction）和构造性证明（constructive proof）也常用于算法下界证明。例如，比较排序的下界 $\Omega(n \log n)$ 通过决策树模型和叶子数至少 $n!$ 的论证，结合斯特林公式（Stirling's approximation）$n! \approx \sqrt{2\pi n}(n/e)^n$ 得出。

概率论基础

概率论为随机算法、平均情况分析和概率数据结构提供了数学工具。本节回顾随机变量、期望、方差、大数定律及切尔诺夫界（Chernoff bound），这些在分析算法期望运行时间或错误概率时不可或缺。

随机变量与分布

随机变量（random variable）$X$ 是定义在样本空间 $\Omega$ 上的实值函数。离散随机变量取值可数，如伯努利试验（Bernoulli trial）的结果。概率质量函数（PMF）$p(x) = \Pr[X=x]$。常见离散分布包括：

• 伯努利分布（Bernoulli distribution）：$\Pr[X=1]=p$，$\Pr[X=0]=1-p$，期望 $E[X]=p$，方差 $\mathrm{Var}[X]=p(1-p)$。
• 二项分布（Binomial distribution）$X \sim \mathrm{Bin}(n,p)$：$n$ 次独立伯努利试验的成功次数，$E[X]=np$，$\mathrm{Var}[X]=np(1-p)$。
• 几何分布（Geometric distribution）：首次成功所需的试验次数，$E[X]=1/p$。
• 泊松分布（Poisson distribution）$X \sim \mathrm{Pois}(\lambda)$：稀有事件发生次数，$E[X]=\lambda$，$\mathrm{Var}[X]=\lambda$。

连续随机变量有概率密度函数（PDF）$f(x)$，累积分布函数（CDF）$F(x)=\Pr[X \leq x]$。常见连续分布包括均匀分布（uniform）、正态分布（normal）、指数分布（exponential）。在算法中，连续分布常用于分析随机化算法或几何概率问题。

期望与方差

期望（expectation）$E[X]$ 是随机变量的加权平均。对于离散 $X$，$E[X] = \sum_x x \cdot p(x)$；对于连续 $X$，$E[X] = \int_{-\infty}^{\infty} x f(x) dx$。期望的线性性质至关重要：无论随机变量是否独立，$E[X+Y] = E[X] + E[Y]$。这简化了复杂随机变量的期望计算，例如分析随机化快速排序的比较次数期望。

方差（variance）$\mathrm{Var}[X] = E[(X - E[X])^2] = E[X^2] - (E[X])^2$，度量偏离期望的程度。标准差（standard deviation）$\sigma = \sqrt{\mathrm{Var}[X]}$。方差的线性性质：若 $X_1,\dots,X_n$ 独立，则 $\mathrm{Var}[\sum_{i=1}^n X_i] = \sum_{i=1}^n \mathrm{Var}[X_i]$。在算法中，方差帮助理解算法运行时间的波动性，例如在随机化算法中，低方差意味着结果更稳定。

大数定律与切尔诺夫界

大数定律（Law of Large Numbers, LLN）表明，大量独立同分布（i.i.d.）随机变量的样本均值收敛于期望值。弱大数定律（Weak LLN）：对任意 $\epsilon > 0$，$\Pr\left[\left|\frac{1}{n}\sum_{i=1}^n X_i - \mu\right| \geq \epsilon\right] \rightarrow 0$ 当 $n \rightarrow \infty$，其中 $E[X_i]=\mu$。强大数定律（Strong LLN）：$\Pr\left[\lim_{n\to\infty} \frac{1}{n}\sum_{i=1}^n X_i = \mu\right] = 1$。在算法中，LLN 解释了蒙特卡罗方法（Monte Carlo method）的收敛性：通过增加随机样本数，估计值趋近真实值。

切尔诺夫界（Chernoff bound）提供了随机变量和偏离期望的指数小上界，比切比雪夫不等式（Chebyshev's inequality）更紧。设 $X = \sum_{i=1}^n X_i$，其中 $X_i$ 独立，$0 \leq X_i \leq 1$，令 $\mu = E[X]$。则对任意 $\delta > 0$：

• 上界：$\Pr[X \geq (1+\delta)\mu] \leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu$
• 下界：$\Pr[X \leq (1-\delta)\mu] \leq \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu$

简化形式：对 $0 < \delta < 1$，$\Pr[X \geq (1+\delta)\mu] \leq e^{-\mu\delta^2/3}$，$\Pr[X \leq (1-\delta)\mu] \leq e^{-\mu\delta^2/2}$。切尔诺夫界在分析随机算法（如随机快速排序、哈希表冲突次数）时极为有用，能证明高概率（high probability）下的良好性能。例如，在 $m$ 个球、$n$ 个桶的哈希分配中，最大桶负载为 $O(\frac{\log n}{\log \log n})$ 以高概率成立。

概率算法分析示例

考虑随机化快速排序（Randomized Quicksort）。其期望比较次数 $E[C_n] = 2(n+1)H_n - 4n \approx 2n \ln n$，其中 $H_n$ 是第 $n$ 个调和数。证明使用指示随机变量（indicator random variable）：设 $X_{i,j}$ 表示元素 $i$ 和 $j$ 在递归过程中被比较的指示变量，则 $C_n = \sum_{1 \leq i < j \leq n} X_{i,j}$。由于 $E[X_{i,j}] = \Pr[\text{第一次选取的主元素在 } i \text{ 和 } j \text{ 之间}] = \frac{2}{j-i+1}$，故 $E[C_n] = \sum_{i<j} \frac{2}{j-i+1} = 2(n+1)H_n - 4n$。方差分析显示 $\mathrm{Var}[C_n] = O(n^2)$，但切尔诺夫界可证 $C_n$ 集中在期望附近，即 $\Pr[|C_n - E[C_n]| \geq \epsilon E[C_n]]$ 指数小。

另一个例子是哈希表链式地址（chaining）。设 $n$ 个元素存入 $m$ 个桶，负载因子 $\alpha = n/m$。最长链长度 $L_{\max}$ 的期望满足 $E[L_{\max}] = \Theta(\frac{\log n}{\log \log n})$ 当 $n$ 大且 $\alpha$ 常数。证明使用切尔诺夫界和并集界（union bound）：对固定桶，链长 $L \sim \mathrm{Bin}(n,1/m)$，$E[L]=\alpha$，则 $\Pr[L \geq k] \leq \binom{n}{k} (1/m)^k \leq (e\alpha/k)^k$。取 $k = c \frac{\log n}{\log \log n}$，该概率为 $n^{-c'}$，对 $m$ 个桶取并集，当 $c$ 足够大时，总概率小于 $1/n$，故以高概率 $L_{\max} = O(\frac{\log n}{\log \log n})$。

递归方程求解

递归方程（recurrence relation）描述算法运行时间的递归结构，是其分析的核心。求解递归方程的标准方法包括递归树（recursion tree）、代入法（substitution method）和主定理（Master Theorem）。本节将系统介绍这些方法，并重点证明主定理及其扩展。

递归树方法

递归树将递归方程展开为树结构，其中节点代表子问题规模，边代表递归调用。树的总代价是所有节点代价之和。此方法直观，但需谨慎处理叶节点和层数。

例如，考虑归并排序的递归方程：$T(n) = 2T(n/2) + cn$，其中 $c$ 为合并代价常数。递归树：根代价 $cn$，第二层两个节点各 $c(n/2)$，总代价 $cn$，第 $i$ 层 $2^i$ 个节点，各 $c n / 2^i$，总代价 $cn$。树高 $\log_2 n$，叶节点数 $n$，各代价 $T(1)=d$，总叶代价 $dn$。故总时间 $T(n) = cn \log_2 n + dn = \Theta(n \log n)$。

更复杂的例子：$T(n) = T(n/3) + T(2n/3) + n$。递归树不完美平衡：左子树规模 $n/3$，右子树 $2n/3$。路径长度最长约 $\log_{3/2} n$，但每层总代价仍为 $n$（因 $n/3 + 2n/3 = n$），故总代价 $O(n \log n)$。严格证明需归纳法或递归树变形。

递归树的优势在于可视化，但需处理非均匀分割或非线性代价。例如 $T(n) = T(\sqrt{n}) + 1$，令 $n=2^m$，则 $S(m)=T(2^m)$ 满足 $S(m)=S(m/2)+1$，解为 $S(m)=\log_2 m + 1$，故 $T(n)=\log_2 \log_2 n + 1$。

代入法

代入法（substitution method）是验证递归方程解的正确性的归纳证明。先猜测解的形式（如 $T(n)=O(n^2)$），然后代入方程验证，必要时调整常数。

例如，猜测 $T(n) = O(n \log n)$ 对归并排序。需证存在 $c>0$ 使 $T(n) \leq c n \log_2 n - d n$（减项处理低阶项）。基础：$T(1)=d_0$，选 $c$ 大使 $c\cdot 1\cdot 0 - d\cdot1 \geq d_0$ 不可能，故需调整形式为 $T(n) \leq c n \log_2 n - b n$，其中 $b$ 待定。归纳：假设对 $k<n$ 成立，则 $$ T(n) = 2T(n/2) + cn \leq 2\left(c \frac{n}{2} \log_2 \frac{n}{2} - b \frac{n}{2}\right) + cn = c n (\log_2 n - 1) - b n + cn = c n \log_2 n - c n - b n + cn = c n \log_2 n - b n. $$ 成立。故 $T(n) \leq c n \log_2 n - b n$，即 $O(n \log n)$。

对于下界，类似证明 $T(n) \geq c' n \log_2 n$。

代入法灵活，但猜测解的形式需经验。常用技巧：递归树给出猜测，或利用已知标准形式。

主定理

主定理（Master Theorem）为形如 $$ T(n) = a T(n/b) + f(n) $$ 的递归方程提供渐近解，其中 $a \geq 1$ 是子问题数，$b > 1$ 是规模因子，$f(n)$ 是划分和合并代价。定义 $n^{\l