反阿克曼函数

概述

反阿克曼函数 $\alpha (n)$ 是一个增长极其缓慢的函数，是不相交集合数据结构在使用按秩合并 + 路径压缩时复杂度分析的核心。它增长得如此之慢，以至于对所有实际可能的输入规模，$\alpha (n)\le 4$，因此在实践中可以视为常数。

定义

快速增长函数 $A_k(j)$

快速增长函数的递归定义

对整数 $k\ge 0,j\ge 0$，定义 $A_k(j)$ 如下： $A_0(j)=2j$ $A_k(0)=0(k\ge 1)$ $A_k(1)=A_{k-1}^{(2)}(1)=A_{k-1}(A_{k-1}(1))(k\ge 1)$ $A_k(j)=A_{k-1}^{(j+1)}(j)=\underset{j+1\text{ 次}}{\underbrace{A_{k-1}(A_{k-1}(\cdots A_{k-1}}}(j)\cdots ))(k\ge 1,j\ge 2)$

其中 $A_{k-1}^{(r)}$ 表示 $A_{k-1}$ 的 $r$ 次复合。

前几层的展开

$k$	$A_k(j)$	含义
$k=0$	$A_0(j)=2j$	线性函数
$k=1$	$A_1(j)=2^j$	指数函数
$k=2$	$A_2(j)=2^{2^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}$（$j$ 个 2）	2 的幂塔，高度 $j$
$k=3$	$A_3(j)$	幂塔的幂塔…，增长速度已无法用常规记号表达
$k=4$	$A_4(j)$	远超任何可想象的计算

反阿克曼函数 $\alpha (n)$ 的定义

反阿克曼函数

$\alpha (n)=\min \{k\ge 1:A_k(1)\ge \lfloor \lg (n+1)\rfloor +1\}$

直观理解：$\alpha (n)$ 是使 $A_k(1)$ 超过 $\lg (n+1)$ 的最小层数 $k$。由于 $A_k(1)$ 随 $k$ 增长得极其快，$\alpha (n)$ 随 $n$ 增长得极其慢。

核心性质

数值表

$n$ 的范围	$\alpha (n)$	说明
$0\le n<2$	1	$A_1(1)=2\ge \lfloor \lg 2\rfloor +1=2$
$2\le n<4$	2	$A_2(1)=4\ge \lfloor \lg 4\rfloor +1=3$
$4\le n<16$	3	$A_3(1)=16\ge \lfloor \lg 16\rfloor +1=5$
$16\le n<2^{65536}$	4	$A_4(1)=2^{65536}$
$n\ge 2^{65536}$	5	需要的 $n$ 大到无法想象

关键事实

对所有实际可能的输入规模，$\alpha (n)\le 4$。即使 $n$ 是一个宇宙中原子数量的指数级，$\alpha (n)$ 仍然不超过 4。$A_4(1)=2^{65536}$ 已经是一个天文数字（远超可观测宇宙中的原子数 $\approx 10^{80}$），而 $A_5(1)$ 更是完全无法用任何物理量来比拟的。

单调性

单调性

$\alpha (n)$ 是一个非递减函数：若 $n_1<n_2$，则 $\alpha (n_1)\le \alpha (n_2)$。

与常数的关系

实践意义

由于 $\alpha (n)\le 4$ 对所有实际 $n$ 成立，在工程实践中：

• $O(m\alpha (n))=O(m)$（实际中）
• 可以安全地将并查集的每次操作视为 $O(1)$
• 但在理论分析中，必须保留 $\alpha (n)$ 以保证严谨性

定理19.14：O(m α(n)) 上界

定理 19.14

在使用按秩合并和路径压缩的不相交集合森林中，对 $n$ 个元素执行 $m$ 次 MAKE-SET、UNION、FIND-SET 操作的序列，总时间为 $O(m\alpha (n))$。

证明方法：使用势能方法。

证明思路概述：

1. 势能函数定义：为每个节点 $x$ 定义势能 $\varphi (x)$，基于 $x$ 的秩和层数 $k=\alpha (n)$。核心思想是将节点按秩分为不同的”级别”（level），级别越高势能越大。

2. 关键引理：对每个级别 $k$，证明在该级别上发生的”代价高昂”的 FIND-SET 操作次数有上界。具体地，级别 $k$ 上的节点被作为 FIND-SET 路径上的非根节点访问的次数不超过某个与 $A_k$ 相关的量。

3. 总代价上界：将所有级别的代价相加，利用 $A_k$ 的快速增长性质，得到总代价 $O(m\alpha (n))$。

详细的证明过程见 CLRS 第4版 Section 19.4，使用了较为复杂的势能函数和分层分析技术。

下界

Fredman & Saks 1989 下界

任何基于比较的并查集实现（仅通过比较元素来决定操作），在 cell-probe 模型下，每次操作的最坏均摊代价为 $\Omega (\alpha (n))$。

这意味着 $O(m\alpha (n))$ 是最优的——不存在渐近更快的基于比较的并查集实现。

直观理解

可以将 $A_k(j)$ 理解为一个”增长速度的层级体系”：

• $A_0$：加法级别（线性增长）
• $A_1$：乘法级别（指数增长）
• $A_2$：幂塔级别
• $A_3$：幂塔的迭代级别
• 每升一级，增长速度发生质变

$\alpha (n)$ 就是问：“要达到 $\lg n$ 这个增长水平，需要用到第几层？“答案是：几乎总是只需要前几层。这就像问”要数到 $n$，需要用到几位十进制数？“——答案是 $\lceil {\lg }_{10}(n+1)\rceil$，增长极其缓慢。

第21章：最小生成树

Kruskal算法的总运行时间 O(E lg V)（排序）+ O(E α(V))（并查集操作）。由于 α(V) ≤ 4 对所有实际 V 成立，并查集部分实际上是线性时间。α(V) 出现在 Kruskal 的总时间界 O(E α(V)) 中，是并查集操作序列的均摊复杂度。

参见

• 不相交集合数据结构 — 并查集的总览
• 按秩合并 — 与路径压缩结合达到 $O(m\alpha (n))$ 的合并策略
• 路径压缩 — 与按秩合并结合达到 $O(m\alpha (n))$ 的查询优化
• 势能方法 — 证明 $O(m\alpha (n))$ 上界使用的均摊分析方法
• 聚合分析 — 加权合并启发式使用的分析方法