并查集的逆 Ackermann 摊还界

形式陈述

定理与约定

对并查集（DSU），考虑 $n\ge1$ 及共 $m\ge n$ 次 Make-Set、Union、Find，其中 $n$ 次 Make-Set 创建 $n$ 个元素。若 Union 总把较低 rank 根挂到较高 rank 根，同 rank 时任选一根并把其 rank 加一；Find 把搜索路径全部改指根，则总时间

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

常简写为 $O(m\alpha(n))$ 。这是对任意合法操作序列成立的摊还保证，不承诺每次 Find 都有逆 Ackermann 的最坏时间。这里 $\alpha$ 是某个固定 Ackermann 层级的逆函数；不同教材的双参数定义相差常数，必须连同定理版本一起固定。

证明骨架

rank 沿父指针严格增加；某个根达到 rank $r$ 时，其集合至少含 $2^r$ 个元素，因此最大 rank 为 $O(\log n)$ 。进一步按合并历史计数，rank 恰为 $r$ 的节点至多有 $n/2^r$ 个：高秩节点虽然可能承担更多后续访问，但数量迅速减少。

逆 Ackermann 分析把父子秩关系按增长极快的阈值划成层级，并将 Find 的工作分摊到操作和节点。压缩让节点改指秩更大的祖先，可推进相应的层级或层内进度；每次 Find 的层级边界访问单独计入该操作，其余访问消耗节点的层内额度。额度依赖节点的秩，再结合各秩节点数的几何衰减求和，得到总访问界。总界同时利用了每次操作经过的层级数和各秩节点能承担的累计费用。

直觉

组合为何必要

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

图中数字是查找路径上的 rank，其他节点省略；分层只表示分析思路，不是完整的 Ackermann 阈值表。底部的界是每操作的摊还界，节点累计费用还要结合其 rank 及各秩节点数求和。

例子与边界

Rollback 边界

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

保证类型与下界

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

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

推论与应用

把并查集用于上层算法时，先统计建集、合并与查找的总次数，再应用这一摊还分析界。定理中的 $m$ 已包含 $n$ 次建集，因而初始化的 $O(n)$ 时间也已计入。

父指针和 rank 数组共占 $O(n)$ 空间。递归 Find 还会使用与压缩前路径等长的调用栈，按秩合并将其深度限制在 $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.
Jeff Erickson, Disjoint Sets, 2013，§16.3–16.5：秩计数与路径压缩分析。

形式陈述 ​

定理与约定 ​

证明骨架 ​

组合为何必要 ​

Rollback 边界 ​

保证类型与下界 ​