算法分析的形式化基础与计算模型

1.1 计算问题的形式化表示与算法的数学定义

算法的有效性首先是一个数学命题，而非经验直觉。当我们说"插入排序比冒泡排序快"时，这一论断只有在问题规模趋于无穷大、特定计算模型被隐式约定、输入分布被限定的前提下才是严谨的。本节的任务，是把这种隐式约定显式化，使后续所有关于"快"与"慢"的讨论都拥有共同的逻辑起点。

1.1.1 计算问题的三层抽象

在最抽象的层面，一个计算问题 $P$ 是一个从输入集合 $I$ 到输出集合 $O$ 的二元关系： $$P \subseteq I \times O$$ 若 $(x, y) \in P$，则称 $y$ 是输入 $x$ 的一个合法解。这一抽象足够宽泛，可以涵盖判定问题（$O = \{0, 1\}$）、搜索问题（$O$ 由 $P$ 决定）以及优化问题（$O$ 中附带代价函数 $c: O \to \mathbb{R}$）。以排序问题为例，可形式化为： $$P_{\text{sort}} = \{(\langle a_1, \ldots, a_n \rangle, \langle b_1, \ldots, b_n \rangle) \mid \{b_1, \ldots, b_n\} = \{a_1, \ldots, a_n\} \land b_1 \le \cdots \le b_n\}$$

第二层抽象涉及编码。算法的输入并非抽象的数学对象，而是有限字母表 $\Sigma$ 上的字符串。通常将整数 $n \in \mathbb{N}$ 用长度为 $\Theta(\log n)$ 的二进制串编码，而将长度为 $n$ 的序列用 $\Theta(n)$ 个分隔符串接。这一看似技术性的细节却决定了复杂度的真值：当编码方式改变时，算法的复杂度可能发生多项式级别的变动。正因如此，复杂度理论将问题视为语言 $L \subseteq \Sigma^*$，并在等价编码下讨论其固有难度。

第三层抽象是实例规模。给定编码方案 $e: I \to \Sigma^*$，实例 $x$ 的规模记为 $|x| = |e(x)|$。规模度量具有平移不变性：对常数 $c > 0$，规模为 $cn$ 的实例其真实工作量应与规模为 $n$ 的实例同阶。若某算法在规模 $n$ 上的运行时间关于 $n$ 是良定义的，那么 $n$ 必须能承载问题所需的所有信息——排序问题中 $n$ 通常指元素个数，而更复杂的图问题中 $n$ 可能指顶点数与边数之和。

1.1.2 算法的形式化定义

依 Church–Turing 论题，一个算法是一个能在有限步骤内对任何输入计算出其合法解的可计算函数。这一论题的非构造性意味着：算法不必被显式实现，但必须存在某个图灵机、λ 演算项或递归函数等价物。然而在复杂度分析中，我们关心的并非"是否可计算"，而是"以何种代价可计算"。因此，需要选择计算模型 $M$，并在 $M$ 上定义基本操作的代价。

为避免读者产生误解，需澄清三个常被混淆的概念。第一，算法是数学对象，与具体编程语言无关；伪代码是描述算法的工具，不应被视为算法本身。第二，复杂度函数 $T_M(n)$ 依赖于计算模型 $M$，但人们通常省略下标，因为主流模型（RAM、图灵机）在多项式级别内具有等价性。第三，复杂度是对算法族的描述，而非单一执行——单次执行时间受输入分布与硬件状态影响，无法作为算法的本质属性。

1.1.3 排序问题的形式化对比

以排序问题为例，可展示同一问题在不同形式化下的复杂度含义。若将排序视为判定问题："给定序列 $a$ 与整数 $k$，是否存在排列 $\pi$ 使得 $a_{\pi(1)} \le \cdots \le a_{\pi(n)}$ 且 $a_{\pi(k)} \ge x$？"——这是一个平凡的多项式时间可解问题，与通常理解的"排序困难"无关。若将排序视为搜索问题："给定序列 $a$，输出其排序结果"——则在比较模型下，$\Omega(n \log n)$ 是已知的下界。这一下界的成立需要：(1) 计算模型是比较模型，即只能通过两两比较获取元素序的信息；(2) 算法须对任意输入正确；(3) 下界论证基于判定树或信息论。一旦放松任一条件，下界便可能失效。这一对比清晰地表明：复杂度结论是三元组 $(\text{问题}, \text{模型}, \text{输入分布})$ 的函数，缺一不可。

1.2 计算复杂度与渐进记号体系

1.2.1 最坏情况、平均情况与最好情况

对算法 $A$ 与计算模型 $M$，记 $T_M^A(x)$ 为输入 $x$ 上的运行时间。给定规模度量 $|\cdot|$，可定义三类复杂度函数： $$T_{\text{worst}}(n) = \max_{|x| = n} T(x), \quad T_{\text{best}}(n) = \min_{|x| = n} T(x)$$ $$T_{\text{avg}}(n) = \mathbb{E}_{x \sim D_n}[T(x)]$$ 其中 $D_n$ 是规模为 $n$ 的输入上的概率分布。本书默认采用最坏情况复杂度 $T_{\text{worst}}(n)$，原因有三：其一，最坏情况不依赖输入分布假设，结论具有普适性；其二，平均情况的分析结果强烈依赖于 $D_n$ 的选取，而实际输入分布往往未知；其三，下界论证通常只能针对最坏情况给出。然而在密码学、机器学习等场景，平均情况分析同样重要，第 12 章将专门讨论。

1.2.2 渐进记号的严格定义

记 $f, g: \mathbb{N} \to \mathbb{R}_{\ge 0}$ 为非负函数。大 $O$ 记号定义为： $$f(n) = O(g(n)) \iff \exists c > 0, n_0 \ge 1, \forall n \ge n_0: f(n) \le c \cdot g(n)$$ 即 $f$ 最终被 $g$ 的常数倍所控制。类似地，大 $\Omega$ 记号： $$f(n) = \Omega(g(n)) \iff \exists c > 0, n_0 \ge 1, \forall n \ge n_0: f(n) \ge c \cdot g(n)$$ 以及大 $\Theta$ 记号： $$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \land f(n) = \Omega(g(n))$$

小 $o$ 与小 $\omega$ 进一步区分"严格小于"与"严格大于"： $$f(n) = o(g(n)) \iff \forall c > 0, \exists n_0, \forall n \ge n_0: f(n) < c \cdot g(n) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$ $$f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$$

需特别强调的是集合论语义：$f = O(g)$ 中 $O(g)$ 表示满足上界性质的函数集合；因此 $2n = O(n)$ 与 $2n \in O(n)$ 等价。链式使用 $f(n) = O(g(n)) = h(n)$ 是允许的，其含义为存在 $f_1$ 使得 $f(n) \le f_1(n)$ 且 $f_1(n) \le c \cdot h(n)$。然而 $f(n) = O(g(n)) = O(h(n))$ 不能解读为 $f$ 既是 $O(g)$ 又是 $O(h)$——这要求 $f$ 同时被两个函数控制，虽然数学上不矛盾但实践中毫无意义。

1.2.3 案例：插入排序与归并排序的严格证明

插入排序的最坏情况复杂度证明：算法对前 $i$ 个元素进行插入操作，每次插入最多比较 $i$ 次并伴随同数量级的元素移动，因此总操作数为： $$T(n) = \sum_{i=2}^{n} (i - 1) = \frac{n(n-1)}{2} = \Theta(n^2)$$ 更精确地，对严格递减输入，每次插入需比较至序列首部，第 $i$ 次插入恰进行 $i-1$ 次比较，故 $T_{\text{worst}}(n) = n(n-1)/2$。由定义，存在 $c = 1/2$ 与 $n_0 = 1$ 使 $T(n) \ge c n^2$，即 $T(n) = \Omega(n^2)$；同时 $c = 1$ 使 $T(n) \le c n^2$，故 $T(n) = O(n^2)$。两者结合得 $T(n) = \Theta(n^2)$。

归并排序的最坏情况复杂度证明：设 $T(n)$ 为排序 $n$ 个元素的最坏时间，则 $$T(n) = 2T(n/2) + \Theta(n), \quad T(1) = \Theta(1)$$ 由递归树分析，第 $k$ 层有 $2^k$ 个子问题，每个规模为 $n/2^k$，合并代价为 $n/2^k$，故该层总代价为 $2^k \cdot (n/2^k) = n$。递归深度为 $\log_2 n$，故总代价为 $n \log_2 n + \Theta(n) = \Theta(n \log n)$。严格证明可对 $n = 2^k$ 用数学归纳法：对 $k = 0$，$T(1) = \Theta(1)$ 成立；假设对规模 $n/2$ 成立，则 $T(n) = 2 \cdot c(n/2)\log(n/2) + cn = cn\log n - cn + cn = cn\log n$，对一般 $n$ 通过取整处理，仍可证 $T(n) = \Theta(n \log n)$。

两者对比揭示了一个核心事实：当 $n \to \infty$ 时，$n \log n \ll n^2$，归并排序在最坏情况下严格优于插入排序。形式上，存在 $n_0$ 使对所有 $n \ge n_0$，归并排序的运行时间严格小于插入排序。这一结论与具体实现、编程语言、硬件平台无关，是算法层面的固有差异。

1.3 平摊分析方法：聚合法、记账法、势能法

最坏情况分析在某些场景下过于悲观。考虑一个动态数组：插入操作在数组未满时为 $O(1)$，但在数组满时触发扩容，需分配新数组并复制全部元素，代价为 $\Theta(n)$。若直接套用最坏情况分析，单次插入代价为 $\Theta(n)$，于是 $n$ 次插入的总代价为 $\Theta(n^2)$。然而直觉告诉我们，由于扩容频率随规模递减，实际总代价仅为 $\Theta(n)$。平摊分析正是为弥合"最坏情况"与"平均表现"之间的鸿沟而设计的方法论。

1.3.1 聚合法

聚合法将 $n$ 次操作的总代价除以 $n$，得到平摊代价。对动态数组场景，每次扩容后数组容量翻倍，故第 $k$ 次扩容发生在元素数为 $2^k$ 时，复制代价为 $2^k$。$n$ 次插入的总代价为： $$T(n) = n + \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \le n + 2n = 3n$$ 故平摊代价为 $T(n)/n = O(1)$。该方法的优点是简洁：只需建立总代价的上界，无需为每种操作单独分配代价。然而其缺点是无法区分不同操作的成本——若数据结构支持多种操作，聚合法无法揭示某些操作更便宜、某些更昂贵的细节。

1.3.2 记账法

记账法（亦称银行家法）为每种操作 $op$ 分配一个平摊代价 $\hat{c}(op)$，使得对任意操作序列： $$\sum_i c_i \le \sum_i \hat{c}_i$$ 其中 $c_i$ 是第 $i$ 次操作的实际代价，$\hat{c}_i$ 是其平摊代价。差额 $\hat{c}_i - c_i$ 视为存入"账户"的信用；账户余额必须始终非负，以保证平摊代价不超过真实代价。

以动态数组为例，设定每次插入的平摊代价为 $3$ 个单位（实际操作 $1$ 用于插入、$2$ 用于未来某次扩容时的复制）。当元素数达到 $2^k$ 时，账户余额为 $2^k \cdot 2 - 2^k = 2^k$（用户多付的部分）减去之前扩容花费的 $2^k$，余额为 $0$；每次扩容后账户重新积累。形式上，第 $j$ 次插入前账户余额非负，故平摊代价 $3$ 是合法的上界。

1.3.3 势能法

势能法通过引入势能函数 $\Phi: \mathcal{S} \to \mathbb{R}_{\ge 0}$（$\mathcal{S}$ 为数据结构状态空间）将记账法抽象化。第 $i$ 次操作的平摊代价定义为： $$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$$ 其中 $D_{i-1}, D_i$ 是操作前后的数据结构状态。累加得： $$\sum_i \hat{c}_i = \sum_i c_i + \Phi(D_n) - \Phi(D_0)$$ 若 $\Phi(D_0) = 0$ 且 $\Phi \ge 0$，则 $\sum_i \hat{c}_i \ge \sum_i c_i$，即平摊代价总和为真实代价总和的上界。势能法的优雅之处在于将"账户余额"的几何直觉提升为函数分析：账户余额即为势能差，扩容前的"存款"对应势能的累积，扩容后的"消耗"对应势能的释放。

对动态数组，定义 $\Phi(D) = 2 \cdot |D| - |C(D)|$，其中 $|D|$ 为当前元素数，$|C(D)|$ 为当前数组容量。初始空数组时 $\Phi(D_0) = 0 - 1 = -1$（取 $|C(D_0)| = 1$），不满足非负性，故需调整为 $\Phi(D) = \max(0, 2|D| - |C(D)|)$。此势能函数的几何含义是：每个数组单元若已存元素则贡献 $2$，若为空则贡献 $0$，未触发的扩容潜力即被量化为势能。每次插入使 $|D|$ 增加 $1$，势能增 $2$，扣除操作代价 $1$，净增 $1$；若未触发扩容则平摊代价为 $3$，若触发扩容则 $|C|$ 翻倍，势能先增 $2$ 后减 $2 \cdot |D|$，合计平摊代价仍为 $3$。

```mermaid flowchart TD A[定义数据结构状态空间 Sigma] --> B[选择候选势能函数 Phi] B --> C{验证 Phi 非负性且 Phi 初始为 0} C -->|不满足| D[调整 Phi 加常数偏移或重定义] D --> B C -->|满足| E[对每种操作 op 计算 amortized cost] E --> F[代入公式 hat_c = c + Phi_after - Phi_before] F --> G[验证所有 amortized cost 为常数上界] G -->|不满足| H[重新选择 Phi 修正] H --> B G -->|满足| I[得出平摊复杂度结论] ```

势能函数的设计是平摊分析的核心技巧。常见的启发式包括：(1) $\Phi$ 度量"未完成的工作量"，如队列中待处理任务数；(2) $\Phi$ 度量"资源积累"，如堆中已分配的剩余空间；(3) $\Phi$ 度量"结构复杂度"，如红黑树的黑高。然而势能函数并非唯一——同一个数据结构常存在多个势能函数，分别揭示不同方面的性质。优秀的势能函数应使所有操作的平摊代价为常数，且与直觉一致。

1.3.4 案例：并查集的平摊分析

并查集（Union-Find）是平摊分析的经典应用。带路径压缩与按秩合并的并查集，单次 Find/Union 操作的平摊代价为 $\alpha(n)$，其中 $\alpha$ 是反 Ackermann 函数，增长极其缓慢。这一结论由 Tarjan 在 1975 年严格证明，是平摊分析史上最重要的结果之一。

具体地，设 $\Phi$ 为按秩合并策略定义的势能函数：$\Phi = \sum_v \log \text{rank}(v)$，其中 $\text{rank}$ 是秩（近似树高）。路径压缩只降低结点的秩，而不增加任何结点的秩，因此 $\Phi$ 单调不增。对按秩合并，每次合并的代价被吸收为 $O(\log n)$；对路径压缩，单次 Find 的平摊代价由 Akk(k) 函数的递推界定。最终结论：$m$ 次操作的总代价为 $O(m \cdot \alpha(n))$，对任何实际可想象的 $n$，$\alpha(n) \le 4$。

1.4 Master 定理及其在分治算法分析中的应用

1.4.1 定理陈述

Master 定理（主定理）处理如下形式的分治递推： $$T(n) = a \cdot T(n/b) + f(n), \quad a \ge 1, b > 1, f(n) \ge 0$$ 其中 $a$ 是子问题数，$n/b$ 是子问题规模（为简化通常设 $n$ 为 $b$ 的幂），$f(n)$ 是分治之外的代价。定义临界指数 $n^{\log_b a}$ 为"叶子代价"，则 $f(n)$ 与 $n^{\log_b a}$ 的相对增长决定了 $T(n)$ 的量级。

定理：设 $T(n) = aT(n/b) + f(n)$，$T(1) = \Theta(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 \ge 0$，则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。
• **情形 3**：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$，对某 $\epsilon > 0$，且对某常数 $c < 1$ 与所有充分大的 $n$ 满足 $a \cdot f(n/b) \le c \cdot f(n)$（正则性条件），则 $T(n) = \Theta(f(n))$。

三种情形分别对应"递归代价占优"、"递归与合并代价同阶"、"合并代价占优"。

1.4.2 应用案例

归并排序：$T(n) = 2T(n/2) + \Theta(n)$，故 $a = 2, b = 2, \log_b a = 1$。$f(n) = \Theta(n) = \Theta(n^1 \log^0 n)$，对应情形 2 中 $k = 0$，故 $T(n) = \Theta(n \log n)$。