并查集的逆 Ackermann 摊还界

定理与约定

从 $n$ 个单元素集合开始，执行 $m\ge n$ 次 Make-Set、Union、Find。若 Union 总把较低 rank 根挂到较高 rank 根，同 rank 时任选一根并把其 rank 加一；Find 把搜索路径全部改指根，则总时间

O\!\left(m\,\alpha(m,n)\right),

常简写为 $O(m\alpha(n))$ 。这里 $\alpha$ 是某个固定 Ackermann 层级的逆函数；不同教材的双参数定义相差常数，必须连同定理版本一起固定。

证明骨架

rank 沿父指针严格增加，且 rank 为 $r$ 的根至少代表 $2^r$ 个元素，所以最大 rank 为 $O(\log n)$ 。更锐利分析把 rank 按飞快增长的 Ackermann 阈值分成 level：路径压缩后，节点父亲的 level 只会上升；同一 level 内父 rank 也只能有限次跨过子级阈值。把 Find 路径边按“造成 level 上升”或“同块前进”收费，每个节点只被收费 $O(\alpha)$ 次。

组合为何必要

只用按秩合并而不压缩，树高最坏 $O(\log n)$ ；只做路径压缩而允许 Union 任意挂接，有不同的摊还界，不能把最终 $\alpha$ 归给单项。实际序列中第一次 Find 可能走长链，后续同路径迅速扁平，正是跨操作收费而非逐次常数。

Rollback 边界

$\alpha(n)$ 增长极慢，却不是数学上的严格常数。可回滚 DSU通常禁用路径压缩，因为一次 Find 会改许多父指针，记录并撤销它们会破坏简单成本；它改用按大小合并的 $O(\log n)$ 最坏高度。该定理也不直接覆盖带删除集合或 fully dynamic connectivity。

保证类型与下界

总界对任意操作序列确定成立，不是随机输入期望；除以 $m$ 才得到每操作 $O(\alpha)$ 摊还。某一次 Find 仍可走 $\Theta(\log n)$ 甚至按变体更长的压缩前路径，不能写成逐次最坏 $\alpha$ 。

在 pointer-machine/链接模型的相应操作集合中，逆 Ackermann 量级有匹配下界，说明“近似常数”不是证明松弛。若允许更强批处理、不同操作或离线知识，模型改变后需重新比较。

一条父链怎样被分层收费

路径压缩执行 find(x) 时，把沿途节点直接连向根；按秩合并保证父节点秩严格增大。分析把秩按 Ackermann 函数增长速度划分层级：节点沿父指针移动时，要么进入更高层，要么在同层跨过足够大的秩区间。前者次数极少，后者可向节点有限的层内额度收费。

对 $m\ge n$ 次操作，总时间为

O\bigl(m\alpha(m,n)\bigr),

这里 $\alpha$ 是二参数逆 Ackermann 函数；写成 $O(m\alpha(n))$ 是常见简化，但不能把它改称严格常数。首次建集的 $O(n)$ 、递归或迭代 find 的栈成本也应计入实现。

只用按秩合并会给 $O(\log n)$ 最坏 find，只用路径压缩也能得到较弱摊还界；逆 Ackermann 结论依赖两者共同作用。可回滚版本通常取消路径压缩，正是用较慢的 $O(\log n)$ 深度换取局部可逆更新。

参考资料

Robert Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, JACM, 1975.
Robert Tarjan, Jan van Leeuwen, Worst-Case Analysis of Set Union Algorithms, JACM, 1984.

定理与约定 ​

证明骨架 ​

组合为何必要 ​

Rollback 边界 ​

保证类型与下界 ​