计算复杂度、渐近记号与计算复杂性理论基础

本篇系统梳理算法分析的基础理论体系，包括计算模型与输入规模度量、渐近符号的数学定义与性质、常见程序结构的复杂度推导、主定理（Master Theorem）的应用，以及计算复杂性理论（P、NP、NP-Hard 与 NP-Complete）的核心概念与归约方法。

---

一、计算模型与输入规模度量

在理论计算机科学中，评估算法效率必须建立在明确的抽象计算模型基础之上。通常采用随机存取机（RAM, Random Access Machine）模型：

• 指令按顺序逐条执行，不存在并发执行；
• 基本操作（算术运算、逻辑运算、比较、内存读写等）均在单位时间内完成，即耗费 $O(1)$ 时间；
• 存储器为无限大小的线性阵列，任意内存单元的访问耗时相同。

1.1 输入规模与位级复杂度

算法的运行时间 $T(n)$ 是输入规模 $n$ 的函数。度量输入规模时需严格区分元素个数与数值大小：

1. 元素集合处理：对含有 $n$ 个元素的数组执行排序或搜索，输入规模即为元素总数 $n$；
2. 大整数运算与数值问题：当输入为一个大整数 $N$（例如素数判定、RSA 模幂计算）时，输入在计算机内部以二进制比特流存储，其真实的输入规模是二进制比特长度：
   $\ell = \lfloor \log_2 N \rfloor + 1 = \Theta(\log N).$

1.2 伪多项式时间（Pseudo-polynomial Time）

设某算法对于输入实例的处理时间为关于某个输入数值参数 $W$ 的多项式（例如 $O(nW)$）。

• 若从数值角度看，形式上表现为多项式；
• 但从实际输入规模（比特长度 $\ell = \Theta(\log W)$）来看，$W = 2^\ell$，其实际运行时间关于输入长度呈指数级增长：$O(n \cdot 2^\ell)$。

这种关于输入数据的“数值大小”呈多项式增长、但关于“输入比特长度”呈指数级增长的算法，被称为伪多项式时间算法。0-1 背包问题的动态规划解法复杂度为 $O(nC)$（$C$ 为背包容量数值），即属于典型的伪多项式时间。

---

二、渐近记号体系：$O, \Omega, \Theta$ 的数学严密定义

为了摆脱具体硬件平台、编译器优化及微架构状态（如缓存命中、分支预测）的干扰，算法分析采用渐近分析（Asymptotic Analysis），重点关注输入规模 $n \to \infty$ 时计算代价的增长阶数。

设 $f(n)$ 与 $g(n)$ 为定义在自然数集上的最终非负函数：

2.1 形式化数学定义

1. 渐近上界 $O$（Big-O）：
   $f(n) = O(g(n)) \iff \exists c > 0, n_0 \in \mathbb{N},\ \forall n \ge n_0:\ 0 \le f(n) \le c \cdot g(n).$
   表明当 $n$ 充分大时，$f(n)$ 的增长速率不超过 $g(n)$ 的常数倍。
2. 渐近下界 $\Omega$（Big-Omega）：
   $f(n) = \Omega(g(n)) \iff \exists c > 0, n_0 \in \mathbb{N},\ \forall n \ge n_0:\ 0 \le c \cdot g(n) \le f(n).$
   表明当 $n$ 充分大时，$f(n)$ 的增长速率不低于 $g(n)$ 的常数倍。
3. 渐近紧确界 $\Theta$（Big-Theta）：
   $f(n) = \Theta(g(n)) \iff \exists c_1, c_2 > 0, n_0 \in \mathbb{N},\ \forall n \ge n_0:\ 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n).$
   数学上，当且仅当 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$ 同时成立时，$f(n) = \Theta(g(n))$。

flowchart LR
    A["渐近下界: Ω(g(n))<br>(至少为该阶数)"] --- B["渐近紧确界: Θ(g(n))<br>(上下界同阶夹逼)"] --- C["渐近上界: O(g(n))<br>(至多为该阶数)"]

2.2 渐近等价性与常数因子的消除

在渐近分析中，所有正乘法常数和低阶加法项均可被渐近记号吸收：

• 为什么 $O(1)$ 与 $O(2)$ 属于同一渐近阶：
  若 $f(n) \le c_1 \cdot 1$，令 $c_2 = c_1 / 2$，则同样满足 $f(n) \le c_2 \cdot 2$。二者刻画的都是“运行时间不随输入规模 $n$ 的增加而增长”的常数时间行为。
• 低阶项的舍弃：
  对于多项式 $f(n) = 3n^2 + 100n + 500$，当 $n \ge 100$ 时，$3n^2 \le f(n) \le 5n^2$。高阶项 $n^2$ 的增长速度在极限意义下完全主导低阶项，因此 $f(n) = \Theta(n^2)$。

2.3 常见渐近复杂度的增长率偏序关系

当 $n \to \infty$ 时，常见复杂度阶数的增长速率由慢到快排列如下：

$$O(1) \prec O(\log n) \prec O(n) \prec O(n\log n) \prec O(n^2) \prec O(n^3) \prec O(2^n) \prec O(n!).$$

需注意的重要极限性质：

• 对任意常数 $k > 0$ 与 $\varepsilon > 0$，对数的多项式次幂增长速度恒严格慢于多项式的任意小正分数次幂，即：
  $\lim_{n\to\infty} \frac{(\log n)^k}{n^\varepsilon} = 0 \implies (\log n)^k = o(n^\varepsilon).$
• 多项式阶无论次数多高，在极限下均被任意底数大于 1 的指数阶压制：$n^k = o(c^n)$（其中 $c > 1$）。

---

三、常见程序结构的时间复杂度推导

3.1 双层嵌套循环与算术级数

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        do_primitive_operation(); // O(1)
    }
}

基本操作的总执行次数为等差数列求和：

$$T(n) = \sum_{i=1}^n \sum_{j=1}^i 1 = \sum_{i=1}^n i = \frac{n(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n = \Theta(n^2).$$

严谨证明应给出级数的代数闭式，而非仅凭“两层循环嵌套”的主观直觉。

3.2 变量倍增循环与对数阶

for (long long i = 1; i <= n; i *= 2) {
    do_primitive_operation();
}

设循环执行了 $k$ 次，循环变量 $i$ 的取值序列为 $1, 2, 4, 8, \ldots, 2^k$。循环终止条件为 $2^k > n$，解得迭代次数为 $k = \lfloor \log_2 n \rfloor + 1 = \Theta(\log n)$。

3.3 收敛几何级数与线性总代价

考虑外层处理规模逐层减半、内层操作代价与当前规模成正比的结构（例如堆排序中的自底向上建堆过程）：

$$T(n) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n \sum_{k=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2}\right)^k < n \sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^k = n \cdot \frac{1}{1 - 1/2} = 2n = \Theta(n).$$

由于公比为 $1/2$ 的几何级数强敛，其累加和被常数 2 严格限制，总计算量为线性的 $\Theta(n)$。与此相对，若内层项为调和级数：
$\sum_{i=1}^n \frac{n}{i} = n \sum_{i=1}^n \frac{1}{i} = n \cdot (\ln n + \gamma + O(1/n)) = \Theta(n\log n).$

---

四、最好、最坏与平均情况复杂度

设 $I_n$ 为规模为 $n$ 的合法输入实例的全集，$T(x)$ 为算法在特定输入 $x \in I_n$ 上执行的基本操作步数：

1. 最坏情况时间复杂度（Worst-case）：
   $T_{\max}(n) = \max_{x \in I_n} T(x).$
   给出算法在任意输入下的绝对性能上限保证，是工程与理论分析中最核心的考查指标。
2. 最好情况时间复杂度（Best-case）：
   $T_{\min}(n) = \min_{x \in I_n} T(x).$
   刻画算法在最理想输入下的表现。
3. 平均情况时间复杂度（Average-case）：
   $E[T](n) = \sum_{x \in I_n} P(x) \cdot T(x).$
   其中 $P(x)$ 为输入 $x$ 出现的先验概率分布（通常假设各合法排列等概率独立出现）。

案例：快速排序（Quick Sort）

• 平均情况：若输入为等概率随机排列，每次划分接近平衡分治，递推式为 $T(n) = 2T(n/2) + \Theta(n)$，平均时间复杂度为 $\Theta(n\log n)$；
• 最坏情况：若每次选取的基准值（Pivot）均为当前序列的极值（例如对已排序数组取首元素为 Pivot），划分退化为子规模 $n-1$ 与 $0$，递推式变为 $T(n) = T(n-1) + \Theta(n)$，最坏时间复杂度急剧恶化为 $\Theta(n^2)$。

[!IMPORTANT]
概念辨析：渐近记号（$O, \Omega, \Theta$）描述的是数学函数的增长阶数，与“最好/最坏/平均情况”属于两个不同正交维度的概念。最坏情况复杂度既可以写出渐近紧确界 $\Theta(n^2)$，也可以在数学上宽松地写为其上界 $O(n^3)$。

---

五、递归递推方程与主定理（Master Theorem）

对于分治算法的标准递推关系式：

$$T(n) = a T(n/b) + f(n),\qquad (a \ge 1, b > 1).$$

该式表达：将规模为 $n$ 的问题拆分为 $a$ 个规模为 $n/b$ 的独立子问题，分解与合并子问题的额外计算代价为 $f(n)$。

5.1 递归树结构与能量博弈

递归树的树高为 $\log_b n$。第 $k$ 层（$k = 0, 1, \ldots, \log_b n$）的子问题总数为 $a^k$，每个子问题规模为 $n/b^k$：

• 树的叶子节点总数为 $a^{\log_b n} = n^{\log_b a}$；
• 算法的渐近效率取决于叶子节点总工作量 $n^{\log_b a}$ 与各层分解合并代价 $f(n)$ 的量级比较。

flowchart TD
    Comp{"比较 f(n) 与 n^(log_b a)"}
    Comp -->|"情况 1: 叶子节点主导<br>f(n) = O(n^(log_b a - ε))"| C1["T(n) = Θ(n^(log_b a))"]
    Comp -->|"情况 2: 各层工作量平衡<br>f(n) = Θ(n^(log_b a) log^k n)"| C2["T(n) = Θ(n^(log_b a) log^(k+1) n)"]
    Comp -->|"情况 3: 顶层根节点主导<br>f(n) = Ω(n^(log_b a + ε)) 且满足正则条件"| C3["T(n) = Θ(f(n))"]

5.2 主定理三类情形的判定与应用

1. 情况 1（叶子主导）：若存在常数 $\varepsilon > 0$，使得 $f(n) = O(n^{\log_b a - \varepsilon})$，则：
   $T(n) = \Theta(n^{\log_b a}).$
   例：$T(n) = 9T(n/3) + n$。此处 $a=9, b=3$，$n^{\log_3 9} = n^2$。因 $f(n) = n = O(n^{2 - 1})$，故 $T(n) = \Theta(n^2)$。
2. 情况 2（各层均衡）：若存在 $k \ge 0$，使得 $f(n) = \Theta(n^{\log_b a} \log^k n)$，则：
   $T(n) = \Theta(n^{\log_b a} \log^{k+1} n).$
   例：归并排序 $T(n) = 2T(n/2) + \Theta(n)$。$a=2, b=2$，$n^{\log_2 2} = n^1$。$f(n) = \Theta(n)$（$k=0$），故 $T(n) = \Theta(n\log n)$。
   例：二分查找 $T(n) = T(n/2) + \Theta(1)$。$a=1, b=2$，$n^{\log_2 1} = n^0 = 1$。$f(n) = \Theta(1)$，故 $T(n) = \Theta(\log n)$。
3. 情况 3（根节点主导）：若存在常数 $\varepsilon > 0$，使得 $f(n) = \Omega(n^{\log_b a + \varepsilon})$，且满足正则条件 $a f(n/b) \le c f(n)$（常数 $c < 1$），则：
   $T(n) = \Theta(f(n)).$
   例：$T(n) = 3T(n/4) + n\log n$。$n^{\log_4 3} \approx n^{0.793}$。$f(n) = n\log n = \Omega(n^{0.793 + 0.2})$，正则性满足，故 $T(n) = \Theta(n\log n)$。

---

六、计算复杂性理论：P、NP、NP-Hard 与 NP-Complete

计算复杂性理论依据问题在特定计算模型下的内在求解难度对问题进行分类。通常聚焦于判定问题（Decision Problem），即输出仅为“是（Yes）”或“否（No）”的问题（优化问题通常可通过引入目标阈值转化为等价的判定问题）。

flowchart TD
    subgraph NP 类问题全集
        P["P 类问题: 确定性图灵机多项式时间内可判定"]
        NPC["NP-Complete (NPC): NP 中最难的判定问题"]
    end
    NPH["NP-Hard (NP 难): 难度不低于任意 NP 问题 (不要求自身属于 NP)"]
    
    P -->|"P ⊆ NP"| NP
    NPC -->|"所有 NP 问题多项式归约至此"| NPH

6.1 核心概念严格界定

1. P 类问题（Polynomial-time）：
   能够在确定性图灵机（Deterministic Turing Machine）上，在关于输入规模的多项式时间 $O(n^k)$ 内被判定的问题集合。
2. NP 类问题（Nondeterministic Polynomial-time）：
   能够在非确定性图灵机上多项式时间内判定的问题集合；或者等价定义为：对于任意回答为“是”的实例，存在一个多项式长度的证书（Certificate），使得确定性图灵机能够在多项式时间内验证该证书的正确性。
   • 注意：NP 的全称为“非确定性多项式”，绝非“非多项式（Non-Polynomial）”。
   • 显然有 $P \subseteq NP$（若一个问题能在多项式时间内直接求解，则该解自身便可充当多项式时间可验证的证书）。
3. 多项式时间归约（Polynomial-time Reduction）：
   设 $A$ 和 $B$ 为两个判定问题。若存在一个多项式时间可计算的映射函数 $f$，使得对于问题 $A$ 的任意实例 $x$：
   $x \in A \iff f(x) \in B,$
   则称问题 $A$ 可以多项式时间归约到问题 $B$，记作 $A \le_p B$。
   • 理论含义：问题 $B$ 的内在计算难度不低于问题 $A$。因为一旦拥有了在多项式时间内求解问题 $B$ 的算法，便可先花多项式时间将实例 $x$ 变换为 $f(x)$，再调用 $B$ 的求解器间接高效解决 $A$。
4. NP 难问题（NP-Hard）：
   若对于所有问题 $L \in \mathrm{NP}$，均满足 $L \le_p H$，则称问题 $H$ 为 NP-Hard 问题（$H$ 自身不必属于 NP 类，也可以不是判定问题）。
5. NP 完全问题（NP-Complete, NPC）：
   若问题 $C$ 同时满足以下两个条件：
   1. $C \in \mathrm{NP}$；
   2. $C \in \text{NP-Hard}$（即 $\forall L \in \mathrm{NP},\ L \le_p C$）。
      则称 $C$ 为 NP 完全问题。

6.2 证明新问题为 NP 完全问题的规范证明方向

若欲证明一个新提出的判定问题 $Y$ 是 NP 完全问题，必须严格执行两步：

1. 证明 $Y \in \mathrm{NP}$：说明如何构造多项式长度的证书，并给出一个在多项式时间内验证证书正确性的确定性算法；
2. 证明 $Y \in \text{NP-Hard}$：选取一个已知的 NP 完全问题 $X$，构造从已知问题 $X$ 到新问题 $Y$ 的多项式时间归约（即证明 $X \le_p Y$）。

[!WARNING]
常见归约方向错误：
很多初学者常将归约方向颠倒，错误地构造了 $Y \le_p X$。$Y \le_p X$ 仅说明“新问题 $Y$ 不比已知难题 $X$ 更难”，完全无法证明 $Y$ 具备 NP-Hard 的难度等级。必须严格遵循“已知 NPC $\le_p$ 待证新问题”的推导方向。

---

七、典型例题与常见易错辨析

7.1 硬件性能提升对不同复杂度问题规模的影响

问题：某算法在当前计算机上 1 小时内可处理规模为 $n$ 的数据。现将计算机运行速度提升 64 倍，求新计算机在 1 小时内能处理的问题规模 $N$。

推导范式：设原运算步数预算为 $T(n)$，新规模 $N$ 满足方程式 $T(N) \le 64 \cdot T(n)$：

1. 若 $T(n) = n$：$N \le 64n$（规模扩大 64 倍）；
2. 若 $T(n) = n^2$：$N^2 \le 64n^2 \implies N \le \sqrt{64}n = 8n$（规模扩大 8 倍）；
3. 若 $T(n) = 2^n$：
   $2^N \le 64 \cdot 2^n = 2^6 \cdot 2^n = 2^{n+6} \implies N \le n + 6.$
   由此可见：面对指数阶算法，即使算力发生巨大翻倍，输入规模也仅能获得常数级加法增加（$+6$），这从根本上解释了为何算法设计必须极力追求多项式时间算法。

7.2 概念辨析自查清单

• 问题 1：$f(n) = O(g(n))$ 是否意味着 $f(n)$ 的运行速度必定快于 $g(n)$？
  • 辨析：否。渐近记号描述的是极限增长率，且定义中允许常数倍数缩放。对于较小的 $n$，$100n$ 可能慢于 $n^2/10$；仅当 $n$ 充分大（$n \ge n_0$）时，渐近阶数的优劣才体现为主导作用。
• 问题 2：若一个问题的最优算法平均运行时间为 $\Theta(n\log n)$，其最坏情况时间复杂度是否可能达到 $\Theta(n^2)$？
  • 辨析：是。平均时间仅为所有输入的概率加权期望。快速排序即为典型代表（平均 $\Theta(n\log n)$，最坏 $\Theta(n^2)$）。
• 问题 3：P 与 NP 的关系是否已确证？
  • 辨析：否。目前数学界普遍猜想 $\mathrm{P} \ne \mathrm{NP}$，但尚未获得严格证明。若能证明任意一个 NP 完全问题属于 P，则直接推出 $\mathrm{P} = \mathrm{NP}$。