理论计算机科学（TCS）中的复杂度分析，核心是渐近分析。它不关心程序在某台具体机器上运行了多少毫秒，而关心当输入规模 \(n\) 趋向无穷大时，算法所需资源（时间或空间）的增长量级。

这就像比较两辆车的长途性能：起步时谁快 0.1 秒并不重要，重要的是随着路程增加，谁的速度优势会越来越大。渐近记号就是描述这种“增长趋势”的数学语言。

1. 五大渐近记号：定义、直觉与运算

1.1 五个记号

这些符号本质上是函数的集合。写作 \(f(n)=O(g(n))\) 时，严格含义是 \(f(n)\in O(g(n))\)，表示函数 \(f\) 属于以 \(g\) 为界的某一类函数。

• \(O\)（大 O）
  • 核心直觉 ： 上界 ，\(f\) 增长不快于 \(g\)。
  • 形式化定义 ：\(\exists c>0,n_0>0\)，使 \(\forall n\ge n_0\)，\(0\le f(n)\le c g(n)\)。
  • 极限视角 ：\(\limsup_{n\to\infty} f(n)/g(n)<\infty\)。
• \(\Omega\)（大 Omega）
  • 核心直觉 ： 下界 ，\(f\) 增长不慢于 \(g\)。
  • 形式化定义 ：\(\exists c>0,n_0>0\)，使 \(\forall n\ge n_0\)，\(0\le c g(n)\le f(n)\)。
  • 极限视角 ：\(\liminf_{n\to\infty} f(n)/g(n)>0\)。
• \(\Theta\)（大 Theta）
  • 核心直觉 ： 紧确界 ，\(f\) 与 \(g\) 同阶。
  • 形式化定义 ：同时满足 \(f=O(g)\) 与 \(f=\Omega(g)\)；即 \(\exists c_1,c_2>0,n_0\)，使 \(c_1g(n)\le f(n)\le c_2g(n)\)。
  • 极限视角 ：\(0<\lim_{n\to\infty} f(n)/g(n)<\infty\)。
• \(o\)（小 o）
  • 核心直觉 ： 严格上界 ，\(f\) 增长严格慢于 \(g\)。
  • 形式化定义 ：\(\forall c>0,\exists n_0>0\)，使 \(\forall n\ge n_0\)，\(0\le f(n)<c g(n)\)。
  • 极限视角 ：\(\lim_{n\to\infty} f(n)/g(n)=0\)。
• \(\omega\)（小 omega）
  • 核心直觉 ： 严格下界 ，\(f\) 增长严格快于 \(g\)。
  • 形式化定义 ：\(\forall c>0,\exists n_0>0\)，使 \(\forall n\ge n_0\)，\(0\le c g(n)<f(n)\)。
  • 极限视角 ：\(\lim_{n\to\infty} f(n)/g(n)=\infty\)。

关键区别：\(O\) 允许“相等”，例如 \(2n^2=O(n^2)\)；而 \(o\) 要求“严格小于”，例如 \(2n=o(n^2)\)。同理，\(\Omega\) 允许相等，\(\omega\) 要求严格大于。

1.2 核心运算规则

加法规则（取主导项）：

\[ O(f(n))+O(g(n))=O(\max(f(n),g(n))) \]

低阶项会被高阶项吸收。例如 \(O(n^2)+O(n)=O(n^2)\)。复杂度分析中通常忽略低阶项和常数系数。

乘法规则：

\[ O(f(n))\cdot O(g(n))=O(f(n)\cdot g(n)) \]

用于处理嵌套结构，例如循环嵌套。

常数因子可忽略：

\[ O(c\cdot f(n))=O(f(n))\quad(c>0\text{ 为常数}) \]

传递性：若 \(f=O(g)\) 且 \(g=O(h)\)，则 \(f=O(h)\)。五个记号都满足相应的传递性。

“等式”的方向性：渐近记号在等式中的用法是不对称的。

• 在等号右边，例如 \(T(n)=2n^2+O(n)\)，表示 \(T(n)\) 等于 \(2n^2\) 加上 某个 属于 \(O(n)\) 集合的匿名函数。
• 在等号左边，例如 \(O(n)=O(n^2)\)，这种写法不规范；通常应理解为集合包含关系 \(O(n)\subseteq O(n^2)\)。

1.3 符号 \(\varepsilon\) 的含义

\(\varepsilon\) 在复杂度理论中不是固定记号，而是一个任意小的正实数，用于表达“严格性”或“任意接近”。

1. 主定理（Master Theorem）中 ：用于区分递归式 \(T(n)=aT(n/b)+f(n)\) 的三种情况。例如 \(f(n)=\Omega(n^{\log_b a+\varepsilon})\) 表示 \(f(n)\) 必须比 \(n^{\log_b a}\) 严格地 高出一个多项式因子，哪怕这个因子是 \(n^{0.001}\)，才能触发主定理第三种情况。
2. 极限定义中 ：经典的“\(\varepsilon\)-\(N\)”语言定义数列极限：对任意 \(\varepsilon>0\)，都存在 \(N\)，使得当 \(n>N\) 时，\(|a_n-L|<\varepsilon\)。
3. 增长阶比较中 ：对任意 \(\varepsilon>0\)，都有 \(\log^k n=o(n^{\varepsilon})\)。这说明任何多项式增长，哪怕指数 \(\varepsilon\) 极小，最终都会超过任何对数多项式增长。

2. 复杂度类与不可判定语言

2.1 常见复杂度类

• \(\mathbf{P}\)： 多项式时间 可解的问题类。存在确定性图灵机在 \(O(n^k)\) 时间内解决，\(k\) 为常数。这被广泛认为是“高效可计算”的理论边界。
• \(\mathbf{NP}\)： 非确定性多项式时间 可解的问题类。通俗地说，如果一个问题的“是”答案能在多项式时间内被 验证 ，那么它属于 NP。
• \(\mathbf{EXP}\)： 指数时间 可解的问题类，即能在 \(O(2^{n^k})\) 时间内解决的问题。
• \(\mathbf{poly}(n)\)：表示“\(n\) 的某个多项式”，即 \(\bigcup_k O(n^k)\)。因此 \(\mathbf{P}=\bigcup_k \mathrm{DTIME}(n^k)=\mathrm{DTIME}(\mathrm{poly}(n))\)。
• \(\mathbf{P/poly}\)： 多项式规模电路 可解的问题类。它包含 \(\mathbf{P}\)，甚至包含 不可判定语言 ，是研究“非一致计算”的重要类别。

2.2 层级关系图

已知 \(\mathbf{P}\subseteq\mathbf{NP}\subseteq\mathbf{PSPACE}\subseteq\mathbf{EXP}\)，并且 \(\mathbf{P}\subseteq\mathbf{P/poly}\)。需要注意：\(\mathbf{P/poly}\) 包含不可判定语言，因此不能简单画成 \(\mathbf{P/poly}\subseteq\mathbf{EXP}\)；\(\mathbf{P/poly}\) 与 \(\mathbf{EXP}\) 不是这种包含关系。

其中绝大多数包含关系是否为真包含，仍是开放问题，尤其是 \(\mathbf{P}\) 与 \(\mathbf{NP}\) 的关系。

2.3 常见增长阶层级

从慢到快，常见增长阶可以排为：

\[ \begin{aligned} O(1)<O(\log^* n)<O(\log\log n)<O(\log n)<O(\sqrt{n})<O(n)\\ <O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)\end{aligned} \]

其中：

• \(\log^* n\) 是 迭代对数 ，增长极慢，出现在并查集相关分析中。
• \(O(n\log n)\) 通常是基于比较的排序算法的下界，例如归并排序。
• \(O(2^n)\) 是典型指数复杂度，常见于暴力搜索子集。

2.4 什么是不可判定语言

一个语言 \(L\)（一组字符串的集合）是可判定的，如果存在一台图灵机，对于任意输入字符串 \(w\)，都能在有限步内停机，并正确回答 \(w\) 是否属于 \(L\)。这台图灵机称为判定器（Decider）。

如果不存在这样的判定器，那么语言 \(L\) 就是不可判定的。这意味着没有任何算法能保证对所有可能输入都给出正确答案；算法可能陷入死循环，或者根本无法定义。

经典例子是停机问题（Halting Problem）：给定程序 \(P\) 和输入 \(x\)，程序 \(P\) 在输入 \(x\) 上最终会停机吗？结论是：不存在通用判定器解决停机问题。

证明思想是对角化论证（Diagonalization），一种自指技巧：

1. 假设存在判定器 \(\mathrm{HALT}(P,x)\)，能正确判断程序 \(P\) 在输入 \(x\) 上是否停机。
2. 构造“捣乱”程序 \(\mathrm{DIAG}(P)\)：如果 \(\mathrm{HALT}(P,P)\) 说 \(P\) 会停机，那么 \(\mathrm{DIAG}\) 故意进入死循环；如果 \(\mathrm{HALT}(P,P)\) 说 \(P\) 不停机，那么 \(\mathrm{DIAG}\) 停机。
3. 问 \(\mathrm{HALT}(\mathrm{DIAG},\mathrm{DIAG})\) 输出什么？无论输出什么，都会与 \(\mathrm{DIAG}\) 自身定义矛盾。
4. 因此最初假设不成立，通用判定器不存在。

另一个经典不可判定语言是通用语言 \(L_u\)，它由所有“图灵机 \(M\) 接受其编码 \(\langle M\rangle\)”的配对组成。\(L_u\) 是递归可枚举的（能被识别，但不保证停机），但不是递归的（不可判定）。

3. 亚指数、阶乘与更狂野的增长

3.1 亚指数增长率

亚指数（Sub-exponential）时间通常指增长慢于任何指数函数 \(2^{\varepsilon n}\)（对任意 \(\varepsilon>0\)）的运行时间，但又快于任何多项式时间。常见形式是 \(2^{O(\sqrt n)}\) 或 \(2^{O(n^\epsilon)}\)，其中 \(0<\epsilon<1\)。

例子：3-SAT 已知存在 \(O(2^{\sqrt n})\) 级别的算法，这是典型亚指数时间算法。指数时间假设（ETH） 推测 3-SAT 不存在 \(2^{o(n)}\) 时间算法；即便 ETH 成立，\(2^{O(\sqrt n)}\) 的算法仍然可能，因为它比 \(2^{o(n)}\) 慢得多。

更精细的层级可以写成：

\[ \begin{aligned}O(1)<O(\log^* n)<O(\log\log n)\\<O(\log n)<O(\sqrt n)<O(n)<O(n\log n)<O(n^2)\\<\cdots<O(n^k)<2^{O(\sqrt n)}<2^{O(n^\epsilon)}<O(2^n)<O(n!)<O(n^n)\end{aligned} \]

加粗区间 \(2^{O(\sqrt n)},2^{O(n^\epsilon)}\) 属于亚指数增长区间。

3.2 为什么 \(2^n=o(n!)\)，以及 \(n!\) 到底算什么

在粗粒度算法分类中，\(2^n\) 和 \(n!\) 常被一起归入“指数级/不可行”。但在严格渐近分析中，\(n!\) 不是固定底数指数复杂度，它比任何 \(c^n\)（\(c>1\) 为常数）增长更快。

比值法：

\[ \frac{n!}{2^n} =\frac{1\cdot2\cdot3\cdots n}{2\cdot2\cdot2\cdots2} =\prod_{i=1}^n \frac{i}{2} \]

从 \(i=3\) 开始，每一项 \(i/2>1\) 且越来越大，因此

\[ \lim_{n\to\infty}\frac{n!}{2^n}=\infty \]

按照小 \(o\) 定义，这正是

\[ 2^n=o(n!) \]

斯特林公式给出更精确刻画：

\[ n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \]

于是

\[ \frac{n!}{2^n}\sim\sqrt{2\pi n}\left(\frac{n}{2e}\right)^n\to\infty \]

这说明 \(n!\) 的“有效底数”是 \(n/e\)，它随 \(n\) 一起增长，而不是固定常数。

严格说，指数复杂度是 \(c^n\)（\(c>1\) 为常数）。而

\[ n!=2^{\Theta(n\log n)} \]

因为 \(n\log n=\omega(n)\)，所以对任意常数 \(c>0\)，都有 \(n!=\omega(c^n)\)。也就是说，阶乘比任何固定底数指数都增长得快，属于超指数增长，但比 \(n^n\) 慢：

\[ \frac{n!}{n^n}\sim\sqrt{2\pi n}\,e^{-n}\to 0 \]

因此精确关系是：

\[ 2^n=o(n!),\qquad n!=o(n^n) \]

而 \(O(2^n)<O(n!)\) 这种写法本身不严谨，因为渐近记号表示集合，不应直接用 < 比较。更准确写法是：

\[ 2^n=o(n!),\qquad O(2^n)\subsetneq O(n!) \]

或写成极限：

\[ \lim_{n\to\infty}\frac{2^n}{n!}=0 \]

“阶乘就是指数复杂度”的说法是工程直觉下的粗粒度分类，在渐近分析中必须区分：\(2^n\subsetneq n!\subsetneq n^n\)。

3.3 比 \(n!\) 更复杂的层级

从 \(n!\) 往上，存在一整套“怪物级”复杂度层级：

\[ n!\ll 2^{2^n}\ll 2\uparrow\uparrow n\ll 2\uparrow\uparrow\uparrow n\ll A(n,n)\ll \text{Conway 链}\ll \text{远超葛立恒数的构造} \]

这些“复杂度”在 TCS 中有两种截然不同的角色：

1. 作为上界 ：某些真实算法的最坏运行时间确实落在这些层级上，例如指数塔、非初等复杂度。
2. 作为构造对象 ：算法本身并不耗时这么多，但它的 输出 是一个大到只能用这些记号表示的数。这类问题更接近“构造性不可行”，而非“不可计算”。

指数塔

双指数 \(2^{2^n}\) 是指数塔最浅的一层，已经超出所有固定层数指数时间类 \(k\text{-EXPTIME}\) 的并集，属于 2-EXPTIME 或更高层级。

真实例子：正则表达式补集的自动机转换。将带否定的正则表达式转换为确定性有限自动机（DFA）时，每嵌套一层否定，DFA 状态数会指数膨胀。对于深度为 \(n\) 的否定嵌套，转换算法运行时间会达到 \(2\uparrow\uparrow\Theta(n)\) 级别，即高度与输入规模成正比的指数塔。即使禁止 Kleene 星号，这个问题仍然是非初等（nonelementary） 的。

高德纳箭头

高德纳箭头是超运算记号体系。单箭头 \(\uparrow\) 是乘方，双箭头 \(\uparrow\uparrow\) 是指数塔（tetration），三箭头 \(\uparrow\uparrow\uparrow\) 是迭代指数塔（pentation），以此类推。\(n\) 个箭头代表 \(n+2\) 级超运算。

如果算法复杂度中箭头数量本身随输入规模增长，就已经进入非初等领域。正则表达式补集转换在更复杂递归否定结构下，运行时间可能达到 \(2\uparrow\uparrow\uparrow\Theta(n)\) 甚至更高。高德纳箭头在这里用于简洁描述非初等上界，而不是说算法真的会“执行箭头运算”。

康威链

康威链式箭头（Conway chained arrow） 是比高德纳箭头更强的增长记号。长度为 3 的链 \(a\to b\to c\) 与高德纳箭头等价：\(a\to b\to c=a\uparrow^c b\)。但链长超过 3 时，康威链能表示高德纳箭头无法简洁表达的大得多的数。

在 TCS 中，康威链极少直接作为“正经算法”的复杂度上界。它更像构造性上界的标尺：如果让算法去计算并输出某个康威链所表示的数，输出这个数的十进制表示本身就需要与之相当的时间。例如计算 \(3\to3\to3\to3\to n\)，其运行时间下界已经远超任何以固定康威链结构为参数的函数。

阿克曼函数

阿克曼函数 \(A(m,n)\) 的增长率超越所有原始递归函数。它的前几层覆盖熟悉运算：\(A(1,n)\) 是加法，\(A(2,n)\) 是乘法，\(A(3,n)\) 是指数，\(A(4,n)\) 是迭代指数（指数塔）。到 \(A(5,n)\) 已经是“超-超指数”，\(A(6,n)\) 被戏称为“无名恐怖”。

阿克曼函数在 TCS 中的重要真实应用是并查集（Union-Find） 的复杂度分析。使用按秩合并与路径压缩的并查集，每次操作摊还时间复杂度是 \(O(\alpha(n))\)，其中 \(\alpha(n)\) 是阿克曼函数的反函数。\(\alpha(n)\) 增长极慢，对任何可想象的实际输入都有 \(\alpha(n)\le4\)，所以并查集“几乎”是线性的。但从理论上看，它的复杂度确实与阿克曼函数直接相关。这说明：阿克曼级别的增长率本身很少成为算法的正向上界，但它的反函数可以成为极其精细的复杂度刻度。

3.4 为什么 FGH 不作为 TCS 的增长率标尺

快速增长层级（Fast-Growing Hierarchy, FGH） 是由序数索引的函数族，用于精确刻画极快增长的可计算函数，在证明论和大数数学中非常有用。但它不适合作为 TCS 中分析算法复杂度的标准标尺。

1. 分辨率不足 ：FGH 的设计目标是攀登增长率的“无限阶梯”，层级之间跨度极大。对于多项式、指数等“常规”增长，FGH 区分度很低。有分析指出，双箭头以下的这些函数，包括多项式、指数、阶乘等，在 FGH 标尺下全部小于 3，几乎没有区分度。这意味着 FGH 无法有效区分 \(n^2\) 和 \(n^3\)，也无法精细区分 \(2^n\) 和 \(n!\)。
2. 定义复杂且依赖基本列 ：FGH 定义涉及序数和基本列。核心递推式 \(f_{\alpha+1}(n)=f_\alpha^n(n)\) 会将 \(f_\alpha\) 迭代 \(n\) 次，导致函数值爆炸性增长。对于极限序数 \(\alpha\)，定义 \(f_\alpha(n)=f_{\alpha[n]}(n)\) 依赖于人为选择的基本列，引入不必要复杂性和非唯一性。
3. 与算法分析目标不匹配 ：TCS 中的 \(O,\Omega,\Theta\) 设计哲学是忽略常数因子和低阶项，聚焦宏观趋势。FGH 追求对函数增长进行极其精细的序数级刻画，超出算法分析实际需求。TCS 需要的是“多项式 vs 指数”这样清晰划分问题难度的界限，而不是 FGH 提供的从指数到迭代指数再到超运算的连续谱。
4. 存在更合适的替代品 ：即便需要比 \(O\) 记号更精细的区分，TCS 也有更合适工具。例如 SGH（缓慢增长层级） 在某些区间比 FGH 有更好分辨率。但本质上，TCS 使用的是 \(O,\Omega,\Theta\) 这一套渐近记号体系，并配合复杂度类（P、NP、EXP、SUBEXP 等）对问题进行分类。

4. 嵌套渐近记号：\(o(2^{n+o(1)})\) 与 \(O(1)\) / \(o(1)\) 的区别

4.1 首先澄清：\(o(1)\) 不是常数复杂度

一个关键符号混淆是：\(o(1)\) 从来不是“常数复杂度”。常数复杂度是 \(O(1)\)，不是 \(o(1)\)。

记号	名称	严格含义	直觉
\(O(1)\)	大 O 常数	存在常数 \(C\)，使 \(f(n)\le C\) 对所有足够大的 \(n\) 成立	有界，不增长
\(o(1)\)	小 o 常数	\(\lim_{n\to\infty}f(n)=0\)	趋于零，最终比任何正常数都小

两者都是函数类，不是常数本身。\(O(1)\) 是被某个常数界住的所有函数，\(o(1)\) 是极限为 0 的所有函数。注意 \(o(1)\subseteq O(1)\)，但反过来不成立。例如 \(f(n)=1\) 属于 \(O(1)\)，但不属于 \(o(1)\)，因为它不趋于 0。

因此，\(o(1)\) 的语义始终是“趋于零的函数类”，不是“常数”。感觉“它不再是常数的语义”，通常是把 \(o(1)\) 和 \(O(1)\) 混淆了。

4.2 \(2^{n+o(1)}\) 的精确含义

严格写法是：

\[ 2^{n+o(1)} \quad\text{表示}\quad \left\{2^{n+f(n)}\;\middle|\;f(n)=o(1)\right\} \]

也就是说，存在某个函数 \(f(n)\)，满足 \(f(n)\to0\)，使得整体是 \(2^{n+f(n)}\)。这里的 \(o(1)\) 不是常数，而是一个匿名的、趋于零的函数；具体是哪个不重要，重要的是它满足“趋于零”这个性质。

具体例子：取 \(f(n)=1/\sqrt n\)，有 \(f(n)=o(1)\)，于是

\[ 2^{n+1/\sqrt n}\in 2^{n+o(1)} \]

取 \(f(n)=1/\log n\) 或 \(f(n)=1/n^2\)，同样成立。\(o(1)\) 可以代表任何趋于零的表达式，例如：

• 多项式衰减：\(1/n,1/n^2\)
• 对数衰减：\(1/\log n,\log\log n/\log n\)
• 根号衰减：\(1/\sqrt n\)
• 更慢的衰减：\(1/\log\log n\)

4.3 重要修正：\(2^{n+o(1)}\) 本身是 \(\Theta(2^n)\)，不是亚指数

因为 \(f(n)=o(1)\)，所以

\[ \frac{2^{n+f(n)}}{2^n}=2^{f(n)}\to1 \]

因此

\[ 2^{n+o(1)}=2^n\cdot(1+o(1))=\Theta(2^n) \]

它不是亚指数，而是渐近标准指数。相应地，

\[ o(2^{n+o(1)})=o(2^n) \]

表示增长严格慢于 \(2^n\) 的函数类，其中可能包括亚指数函数，也可能包括多项式函数。真正常见的亚指数写法是：

\[ 2^{o(n)},\qquad 2^{n^{o(1)}} \]

或者用复杂度类

\[ \mathbf{SUBEXP}=\bigcap_{\varepsilon>0}\mathrm{DTIME}\left(2^{n^\varepsilon}\right) \]

4.4 \(2^{n+o(1)}\) 与 \(2^{n+O(1)}\) 的对比

表达式	指数部分偏差	含义
\(2^{n+o(1)}\)	\(f(n)\to0\)	整体为 \(2^n\cdot2^{o(1)}=2^n\cdot(1+o(1))\)，即渐近等于 \(2^n\)，相对误差趋于 0
\(2^{n+O(1)}\)	\(f(n)\) 有界，\( | f(n) | \le C\)	整体为 \(2^n\cdot2^{O(1)}=2^n\cdot\Theta(1)\)，即与 \(2^n\) 同阶，但相对误差可能不趋于 0

关键区别：\(o(1)\) 要求偏差消失，\(O(1)\) 只要求偏差有界。因此

\[ 2^{n+o(1)}\subsetneq 2^{n+O(1)} \]

前者比后者更紧。

4.5 其他类似嵌套写法

• \(2^{O(n)}\)：增长不快于 \(2^{cn}\)（某个常数 \(c\)）的函数类，是标准指数上界。
• \(2^{\Theta(n)}\)：增长与 \(2^{cn}\)（某个常数 \(c\)）同阶的函数类。
• \(2^{o(n)}\)：亚指数复杂度，即对任意 \(\varepsilon>0\)，增长都慢于 \(2^{\varepsilon n}\) 的函数类。
• \(n^{O(1)}\)：多项式上界，即存在常数 \(c\) 使函数属于 \(O(n^c)\)。
• \(n^{o(1)}\)：增长慢于任何多项式的函数类，例如 \(\log n\)，因为对任意 \(\varepsilon>0\)，\(\log n=o(n^\varepsilon)\)。

5. 多项式电路与 \(\mathbf{P/poly}\)

5.1 电路族

电路族是一个无限电路序列 \((C_n)_{n\in\mathbb N}\)，其中对每一个输入长度 \(n\)，都有一个布尔电路 \(C_n\)，它恰好有 \(n\) 个输入位和一个输出位。电路由与门、或门、非门等逻辑门构成的有向无环图。

5.2 多项式电路的定义

一个语言 \(L\subseteq\{0,1\}^*\) 具有多项式电路，如果存在一个多项式电路族 \((C_n)_{n\in\mathbb N}\) 能够判定 \(L\)。

这里的“多项式电路族”指：存在多项式 \(p(n)\)，使得对每一个 \(n\)，电路 \(C_n\) 的大小（逻辑门数量）都不超过 \(p(n)\)。所有这类语言的集合构成复杂度类 \(\mathbf{P/poly}\)。

5.3 非一致性

多项式电路模型是非一致的（non-uniform）。对不同输入长度 \(n\)，对应电路 \(C_n\) 可以完全不同，并且生成这些电路的算法本身可能不存在或不可计算。这与图灵机模型（一致模型）形成对比：图灵机中同一个程序处理所有长度输入。正是这种非一致性，使得 \(\mathbf{P/poly}\) 能够包含不可判定语言——例如可以为每个长度 \(n\) 设计一个“硬编码”了某个不可判定问题答案的电路。

6. 并查集：从数学定义到反阿克曼函数

6.1 数学定义

并查集（Union-Find / Disjoint Set Union, DSU）维护全集 \(U=\{1,2,\dots,n\}\) 上的一个划分（Partition），即将 \(U\) 分成若干互不相交的子集。

它支持三种基本操作：

1. MakeSet(x) ：创建一个只包含元素 \(x\) 的新集合。初始时每个元素自成一个集合。
2. Find(x) ：返回元素 \(x\) 所在集合的 代表元（Representative） 。两个元素属于同一集合，当且仅当 Find(x)==Find(y) 。
3. Union(x,y) ：将元素 \(x\) 和 \(y\) 所在的两个集合合并为一个新集合。

图论视角：每个集合表示为一棵有根树。节点是集合中的元素，根节点就是该集合的代表元。Find 沿父指针走到根；Union 将一棵树的根连接到另一棵树的根上。

6.2 两大核心优化

不加优化时，Union 可能将一棵很高的树嫁接到单节点上，形成长链，使后续 Find 退化为 \(O(n)\)。

按秩合并（Union by Rank）

核心思想：合并时总是将“较矮”的树连接到“较高”的树下，避免树高失控。

• 秩（Rank） ：每个根节点维护一个秩，作为树高的 上界 。初始为 0。两棵秩相同的树合并时，新根的秩才加 1。
• 效果：仅使用此优化，树高可控制在 \(O(\log n)\) 以内。
• 变体：也可以按 大小（Size） 合并，即节点数少的树连接到节点数多的树下，效果类似。

路径压缩（Path Compression）

核心思想：执行 Find(x) 时，将查找路径上所有节点直接挂到根节点下，从而“压平”树结构。

• 机制：找到根后，让路径上每个节点（包括 \(x\) 本身及其所有祖先）的父指针直接指向根。
• 效果：后续对这些节点的 Find 几乎在常数时间内完成。
• 路径压缩 不会改变任何节点的秩 ，因为它只改变树的结构，不改变“合并历史”所隐含的高度上界。

6.3 操作分工图

Union 和 Find 是两个独立基本操作，加上 MakeSet 共三个。按秩合并是 Union 的策略，路径压缩是 Find 的策略。但 Union 内部会调用 Find 来定位根，因此两个操作在实践中紧密交织：每次 Union 都先触发两次路径压缩，再执行一次按秩挂接。

6.4 复杂度：反阿克曼函数

优化策略	单次操作摊还复杂度
无优化（朴素）	\(O(n)\) 最坏
仅按秩合并	\(O(\log n)\)
仅路径压缩	\(O(\log n)\) 摊还
按秩合并 + 路径压缩	\(O(\alpha(n))\)

其中 \(\alpha(n)\) 是反阿克曼函数（Inverse Ackermann Function）。阿克曼函数 \(A(m,n)\) 增长极其恐怖，远超指数塔，因此反函数 \(\alpha(n)\) 增长极其缓慢。对于任何实际物理世界中可能出现的 \(n\)，例如宇宙原子总数，\(\alpha(n)\) 的值都不超过 4。因此并查集操作在实践中可以认为近乎常数时间。

包含 \(m\) 次操作、\(n\) 个元素的完整操作序列，总时间上界为：

\[ O(m\cdot\alpha(n)) \]

6.5 为什么不是 \(O(1)\)，以及 \(\alpha(n)\le4\) 的含义

路径压缩确实在疯狂压平树，但有一个微妙误解：路径压缩只压平它访问过的那条路径，而不是整个集合。它不会自动压平其他未被 Find 触及的分支，而且后续 Union 会不断引入新的深度。

具体场景：当前有一棵由按秩合并构造出的树，高为 \(O(\log n)\)。调用 Find(x)，其中 \(x\) 是深叶子。路径压缩会沿 \(x\) 到根的路径，把所有节点直接挂到根下，这条路径被彻底压平。但是，这棵树上其他分支，那些不在 \(x\) 路径上的节点，深度完全没有变化。更关键的是，后续 Union 可能把新的单节点挂到一个很深的节点下面。这个新节点加入瞬间深度就很大，而它还没有被任何 Find 访问过，所以保持深。

所以，“压平”是局部的、按需的：只有被 Find 走过的路才会变平。未被访问的路径保持原样，而 Union 会持续制造新的深路径。这就是为什么不能断言“永远摊平”。

如果每次操作都能把整棵树彻底压平，那确实 \(O(1)\) 就够了。但路径压缩的效力有代价，需要精细记账。Tarjan 在 1975 年的分析揭示：

1. 路径压缩的总“压平量”是有限的。每次 Find 走过的路径长度会被压缩掉，但这个压缩效果不会无限累积，因为 Union 会不断往树里添加新边，重新引入深度。
2. 按秩合并保证树高上界是 \(O(\log n)\)，但路径压缩后实际高度远低于此。问题是下界能低到什么程度。Tarjan 证明存在一列操作序列，使总时间达到 \(\Omega(m\cdot\alpha(n))\)，也就是说 \(\alpha(n)\) 是紧的，不能进一步改进为常数。
3. \(\alpha(n)\) 定义为阿克曼函数 \(A(k,k)\) 的反函数。阿克曼函数增长极快，所以 \(\alpha(n)\) 增长极慢。\(\alpha(n)\le4\) 对几乎所有实际输入成立，但理论上 \(\alpha(n)\) 是无界的；随着 \(n\) 增大，它最终会超过 4、5、6……只是需要 \(n\) 大到天文数字级别。

这里的“4”不是“每次操作需要 4 步”，而是说：对于所有 \(n<A(4,4)\)，反阿克曼函数的值不超过 4。而 \(A(4,4)\) 是一个高度为 65536 的 2 的指数塔，远远超过宇宙原子总数。所以对所有可想象输入，\(\alpha(n)\le4\)。因此摊还复杂度 \(O(\alpha(n))\) 在实践中等价于 \(O(1)\)，但理论上它是一个缓慢增长的无界函数。关键区别：\(O(1)\) 意味着存在固定常数对所有 \(n\) 成立；\(O(\alpha(n))\) 意味着常数随 \(n\) 缓慢增长，只是增长得极其缓慢。

为什么不能做到真正的 \(O(1)\)？一个直观解释来自信息论下界：并查集需要维护 \(n\) 个元素的划分，可能的划分数量是贝尔数 \(B_n\)，增长极快。任何数据结构要在 \(O(1)\) 时间内支持任意 Union 和 Find，就需要在常数时间内编码巨量状态信息，这在比较模型下不可能。Tarjan 的下界证明正是从这个角度出发：任何基于比较的并查集算法，其摊还时间下界是 \(\Omega(\alpha(n))\)。换句话说，\(\alpha(n)\) 不是算法“不够好”的产物，而是问题本身的内在难度；路径压缩 + 按秩合并已经达到这个下界，因此是最优的。

6.6 “Union 会创造新叶子”的精确解释

Union 不创建新节点（节点数固定），但它确实会“创造”新的深节点——让一些原本很浅的节点，甚至刚被路径压缩压平的节点，重新变深。

核心原因：路径压缩和 Union 是两种完全独立、作用方向相反的操作。路径压缩在局部压平，而 Union 在全局系统性地增加深度。两者交替进行，形成“破坏—修复”的动态平衡，这正是 \(\alpha(n)\) 的根源。

Union(x,y) 的标准流程：

1. 对 \(x\) 和 \(y\) 分别调用 Find ，找到两个根 \(r_x,r_y\)。
2. 比较两者秩，将秩较小的根挂到秩较大的根下面。

关键在第二步：当一棵树 \(T\) 的根被挂到另一棵树下时，\(T\) 中所有节点的深度都加 1，包括 \(T\) 里那些刚刚被路径压缩压平过的节点。Union 不会遍历被挂树的所有节点去更新深度，它只改一个指针，把 \(r\) 的父指针指向 \(R\)。但效果上，\(r\) 下面整棵子树的深度都增加了 1。这些节点中有些可能刚被 Find 压平过，现在又变深了；路径压缩的成果被 Union 部分抵消。

“新叶子”出现的三种典型场景：

1. 新元素加入 ： MakeSet(x) 创建深度为 0 的单节点。随后 Union(x,y) 把它挂到一棵很深的树下，这个新节点瞬间获得很大深度，而它从未被任何 Find 访问过，路径压缩对它完全无效。
2. 被挂树的整棵子树变深 ：一棵树 \(T\) 之前被多次 Find 压得很扁，但它的秩仍然较高，因为秩只增不减，记录的是历史合并次数。当 \(T\) 被挂到另一棵秩更高的树下时，\(T\) 中所有节点，包括被压平过的，深度全部加 1。路径压缩的局部成果被整体平移。
3. 按秩合并的秩是上界，不是实际高度 ：秩记录树高上界，不是当前实际高度。一棵被路径压缩压得很矮的树，秩可能仍然很高。两棵秩相同的树合并时，其中一棵被挂到另一棵下，被挂的那棵实际可能很矮，但挂上去之后整棵子树都变深了。秩的保守性导致 Union 有时会做出“实际不必要”的加深操作。

路径压缩不能“防住” Union，因为两者时机和范围不同：

	路径压缩	Union
触发时机	只在 Find 时	每次合并时
作用范围	只压平被访问的那条路径	让整棵被挂子树深度加 1
是否遍历全树	否，只走一条路径	否，只改一个指针，但效果波及整棵子树
方向	减少深度	增加深度

路径压缩是按需的、局部的、被动的；Union 是主动的，效果上是全局的。只要还有 Union 发生，深度就会被系统性重新引入。路径压缩只能“追赶”被 Find 访问到的路径，无法预防 Union 在未来制造的深度。

这种“压平—加深—再压平—再加深”的拉锯战，使总时间既不是线性的，因为 Union 持续制造深度，也不是每次 \(O(1)\)，因为 Find 偶尔要走过长路径。精确平衡点就是 \(\alpha(n)\)，它刻画了在 \(m\) 次操作中，每个节点平均被“重新加深”和“重新压平”的次数。

6.7 单次最坏与摊还：能否构造“奇葩”情况

可以构造操作序列，让其中某一次 Find 操作付出较高代价，但这不会推翻 \(\alpha(n)\) 的摊还上界。关键是区分摊还复杂度（Amortized Complexity） 和最坏情况单次操作复杂度（Worst-case per-operation Complexity）。

\(\alpha(n)\) 描述的是一整套操作序列的总代价被平均到每次操作上的结果。它允许序列中个别操作异常昂贵，只要这些昂贵操作出现频率足够低，总账依然划算。

Tarjan 的 \(O(m\cdot\alpha(n))\) 是序列总时间上界。它说的是，对任意包含 \(m\) 次操作的序列，总代价不超过 \(c\cdot m\cdot\alpha(n)\)。这并不保证序列中每一次 Find 都在 \(O(\alpha(n))\) 内完成。单次 Find 的代价取决于需要遍历的路径长度。在按秩合并约束下，树的最大高度是 \(O(\log n)\)，所以单次 Find 最坏是 \(O(\log n)\)。如果缺少按秩合并、只有路径压缩，单次 Find 才可能达到 \(O(n)\)。在一次 Find 触发大规模压平之前，树中可能积累出一条较长路径，使这一次 Find 的代价达到 \(O(\log n)\)；这次操作会把路径上所有节点直接挂到根上，使后续对这些节点的 Find 变得极其廉价。摊还分析正是利用“昂贵操作为自己预付未来成本”的特性，将一次性高代价分摊到后续一系列廉价操作上。

构造“单次昂贵”序列的思路：

1. 利用 Union 积累深度 ：路径压缩只在 Find 时发生。连续执行大量 Union ，中间不穿插任何 Find ，路径压缩就没有机会压平结构。按秩合并虽然限制高度上界为 \(O(\log n)\)，但在达到上界前，树高可以持续增加。
2. 选择深处叶子节点 ：这些 Union 完成后，树中存在一些深度较大的节点。此时对其中一个从未被 Find 访问过的、位于最深路径末端的叶子节点调用 Find ，这次查找必须沿长路径走到根，代价可达 \(O(\log n)\)。
3. 代价与收益 ：这次 Find 的代价与路径长度成正比。但作为副作用，它会把这条长路径上的所有节点一次性全部压平，直接挂到根下。这次昂贵操作实际上是在为未来“投资”，让路径上所有节点在后续操作中几乎 \(O(1)\) 可达。

这正是“Union 会创造新叶子”的精确图景：Union 在不断制造深度，Find 在消化深度。可以精心安排操作顺序，让“制造”和“消化”在时间上严重错位，从而制造单次高峰。

但总账无法突破 \(\alpha(n)\)。Tarjan 下界证明存在一列操作序列，其总时间达到 \(\Omega(n\cdot\alpha(n))\)，因此 \(\alpha(n)\) 不是可随意改进的宽松上界，而是紧的刻画。Fredman 和 Saks 在 1989 年进一步证明，在任何基于比较的模型下，这个下界无法被突破。不存在一个通用操作序列，能让按秩合并与路径压缩的并查集在总时间上超越 \(\Theta(m\cdot\alpha(n))\) 的量级。每次 \(O(\log n)\) 的 Find 之后，路径上那批节点在后续操作中会变得极其廉价，这种压平带来的巨额折扣会迅速拉低平均成本。无法让整个系统持续地以高于 \(\alpha(n)\) 的摊还成本运行，因为路径压缩的总“压平潜力”有限，而 \(\alpha(n)\) 精确描述了这种潜力的消耗速率。

6.8 严格证明的大致结构：势能法

这个上界的严格证明核心工具是势能法（Potential Method）。它不直接追踪每次 Find 走了多少步，而是为整个数据结构定义“势能”，证明：单次操作实际代价 + 势能变化 ≤ 某个摊还上界。如果势能永远非负，那么总摊还代价就是总实际代价的上界。

证明结构大致是：用“秩”搭建层级，用“层级”定义势能，最终让 \(\alpha(n)\) 从层级数量的上界中自然浮现。

第一步：用秩搭建层级系统

起点是按秩合并保证的性质：一个节点的秩一旦停止作为根，就永远不会再改变。一个秩为 \(k\) 的根节点，必然是合并了两个秩至少为 \(k-1\) 的根才诞生的。这意味着秩越高的节点“资历”越深，其下挂着的子树规模呈指数级增长。

基于秩，Tarjan 的原始证明引入辅助函数，通常记为 \(\mathrm{level}(x)\) 或 \(l(x)\)。它衡量从节点 \(x\) 出发沿父指针向上，其父节点的秩相对于 \(x\) 自身的秩能“跳跃”多少级。这个 level 函数把所有节点划分进至多 \(\alpha(n)\) 个“层级”。\(\alpha(n)\) 在这里第一次作为“层级总数”的上界出现，而不是凭空产生。

第二步：构造势能函数

定义势能函数 \(\Phi\)，让它在 Find 压平路径时大幅下降，从而“支付”这次查找的实际成本。一种常见定义是：

\[ \Phi(x)=(\alpha(n)-\mathrm{level}(x))\cdot\mathrm{rank}(x)-\mathrm{iter}(x) \]

其中 \(\mathrm{iter}(x)\) 是另一个更精细的辅助函数。

这个势能函数的设计精妙之处：

• 对于 Find 路径上的节点，路径被压缩时，这些节点的父节点发生改变，它们的 level 或 iter 值会显著降低，导致势能大幅减少。势能减少量恰好可以抵消这次 Find 遍历路径的实际代价。
• 对于 Union 操作，合并只影响两个根节点，势能总变化可控制在 \(O(\alpha(n))\) 以内，因此 Union 摊还代价很小。

整个分析变成记账过程：Find 的昂贵代价由势能“支出”覆盖；Union 只产生微小“收入”。只要保证势能始终非负，总“支出”就不会超过总“收入”加初始势能。

第三步：汇总账本

每次 Union 的摊还代价是 \(O(\alpha(n))\)。每次 Find 的摊还代价，在势能分析支付下，也被摊平到 \(O(\alpha(n))\)。因此对于 \(m\) 次操作，总摊还时间为：

\[ O(m\cdot\alpha(n)) \]

这就是 Tarjan 在 1975 年证明的核心结论。

下界：为什么紧

Fredman 和 Saks 在 1989 年证明下界：在任何基于比较的模型中，并查集问题本身就需要 \(\Omega(m\cdot\alpha(n))\) 的摊还时间。他们的证明思路是时间 Chronogram 技术，不分析具体算法，而从信息论角度构造“难”的操作序列，证明任何数据结构只要行为只依赖元素间比较结果，就必然要花费这么多时间。这不是 Tarjan 算法“恰好”达到这个界，而是问题本身的内在难度就是 \(\alpha(n)\)，而按秩合并 + 路径压缩已经触及理论天花板。

6.9 并查集的实际应用

1. 克鲁斯卡尔算法（Kruskal’s Algorithm）求最小生成树 ：将所有边按权重升序排序，依次考察边 \((u,v)\)。用 Find(u) 和 Find(v) 判断两端点是否已连通。若不连通，加入生成树并 Union(u,v) ；若已连通，跳过。并查集高效实现“环检测”和“连通分量合并”。
2. 动态连通性问题 ：在持续加入新连接的过程中，快速回答任意两个节点当前是否连通。例如社交网络判断两个用户是否属于同一“朋友圈”；计算机网络中动态追踪两台主机是否在同一子网；图像分割中根据颜色或纹理相似度合并区域。
3. 编译器设计中的合一（Unification） ：在类型推断或逻辑编程（如 Prolog）中，合一算法需要判断两个项是否能通过变量替换变得相同。并查集可高效维护变量之间的等价关系。
4. 维护连续区间 ：动态维护数轴上连续被“激活”的段。每个位置视为节点，位置被激活时用 Union 与相邻已激活位置合并，高效维护区间连通性。

并查集的精妙之处在于，它用极简的树形结构，配合两个巧妙的启发式规则，实现了理论上的近乎最优的动态集合管理。

7. 总结

• 渐近记号 \(O,\Omega,\Theta,o,\omega\) 提供了一套忽略常数与低阶项、聚焦增长趋势的严谨语言。核心运算规则是加法取最大、乘法做乘积。\(o(1)\) 是趋于零的函数类，\(O(1)\) 才是有界常数类。
• \(\varepsilon\) 用于表达严格性、任意小间隙，在主定理、极限定义、对数与多项式比较中反复出现。
• 复杂度类 P、NP、EXP、P/poly 描述问题整体难度；P/poly 是非一致模型，甚至包含不可判定语言。
• 不可判定语言揭示了计算的绝对极限；停机问题和对角化是经典入口。
• 亚指数 \(2^{O(\sqrt n)}\)、\(2^{O(n^\epsilon)}\) 填补多项式与指数之间；\(2^{n+o(1)}\) 本身是 \(\Theta(2^n)\)，不是亚指数；\(o(2^{n+o(1)})=o(2^n)\)。
• \(n!\) 不是固定底数指数，而是 \(2^{\Theta(n\log n)}\)，满足 \(2^n=o(n!)\)、\(n!=o(n^n)\)。
• 指数塔、高德纳箭头、康威链、阿克曼函数描述了更狂野的增长层级；FGH 因分辨率、定义复杂性和目标不匹配，不适合作为 TCS 增长率标尺。
• 并查集通过按秩合并与路径压缩达到 \(O(m\cdot\alpha(n))\) 的摊还复杂度；单次最坏在按秩合并下为 \(O(\log n)\)，摊还总账由势能法证明，并由 Fredman-Saks 下界确认其紧性。