并查集复杂度

本部分内容转载并修改自时间复杂度 - 势能分析浅谈，已取得原作者授权同意。

定义

阿克曼函数

这里，先给出 $α (n)$ 的定义。为了给出这个定义，先给出 $A_{k} (j)$ 的定义。

定义 $A_{k} (j)$ 为：

A_{k} (j) = {\begin{aligned} j + 1 & k = 0 \\ A_{k - 1}^{(j + 1)} (j) & k \geq 1 \end{aligned}

即阿克曼函数。

这里， $f^{i} (x)$ 表示将 $f$ 连续应用在 $x$ 上 $i$ 次，即 $f^{0} (x) = x$ ， $f^{i} (x) = f (f^{i - 1} (x))$ 。

再定义 $α (n)$ 为使得 $A_{α (n)} (1) \geq n$ 的最小整数值。注意，我们之前将它描述为 $A_{α (n)} (α (n)) \geq n$ ，反正他们的增长速度都很慢，值都不超过 4。

基础定义

每个节点都有一个 rank。这里的 rank 不是节点个数，而是深度。节点的初始 rank 为 0，在合并的时候，如果两个节点的 rank 不同，则将 rank 小的节点合并到 rank 大的节点上，并且不更新大节点的 rank 值。否则，随机将某个节点合并到另外一个节点上，将根节点的 rank 值 +1。这里根节点的 rank 给出了该树的高度。记 x 的 rank 为 $r n k (x)$ ，类似的，记 x 的父节点为 $f a (x)$ 。我们总有 $r n k (x) + 1 \leq r n k (f a (x))$ 。

为了定义势函数，需要预先定义一个辅助函数 $l e v e l (x)$ 。其中， $l e v e l (x) = max (k : r n k (f a (x)) \geq A_{k} (r n k (x)))$ 。当 $r n k (x) \geq 1$ 的时候，再定义一个辅助函数 $i t e r (x) = max (i : r n k (f a (x)) \geq A_{l e v e l (x)}^{i} (r n k (x))$ 。这些函数定义的 $x$ 都满足 $r n k (x) > 0$ 且 $x$ 不是某个树的根。

上面那些定义可能让你有点头晕。再理一下，对于一个 $x$ 和 $f a (x)$ ，如果 $r n k (x) > 0$ ，总是可以找到一对 $i, k$ 令 $r n k (f a (x)) \geq A_{k}^{i} (r n k (x))$ ，而 $l e v e l (x) = max (k)$ ，在这个前提下， $i t e r (x) = max (i)$ 。 $l e v e l$ 描述了 $A$ 的最大迭代级数，而 $i t e r$ 描述了在最大迭代级数时的最大迭代次数。

对于这两个函数， $l e v e l (x)$ 总是随着操作的进行而增加或不变，如果 $l e v e l (x)$ 不增加， $i t e r (x)$ 也只会增加或不变。并且，它们总是满足以下两个不等式：

0 \leq l e v e l (x) < α (n)

1 \leq i t e r (x) \leq r n k (x)

考虑 $l e v e l (x)$ 、 $i t e r (x)$ 和 $A_{k}^{j}$ 的定义，这些很容易被证明出来，就留给读者用于熟悉定义了。

定义势能函数 $Φ (S) = \sum_{x \in S} Φ (x)$ ，其中 $S$ 表示一整个并查集，而 $x$ 为并查集中的一个节点。定义 $Φ (x)$ 为：

Φ (x) = {\begin{cases} α (n) \times rnk (x) & rnk (x) = 0 或 x 为某棵树的根节点 \\ (α (n) - level (x)) \times rnk (x) - i t e r (x) & otherwise \end{cases}

然后就是通过操作引起的势能变化来证明摊还时间复杂度为 $Θ (α (n))$ 啦。注意，这里我们讨论的 $u n i o n (x, y)$ 操作保证了 $x$ 和 $y$ 都是某个树的根，因此不需要额外执行 $f i n d (x)$ 和 $f i n d (y)$ 。

可以发现，势能总是个非负数。另，在开始的时候，并查集的势能为 $0$ 。

证明

union(x,y) 操作

其花费的时间为 $Θ (1)$ ，因此我们考虑其引起的势能的变化。

这里，我们假设 $r n k (x) \leq r n k (y)$ ，即 $x$ 被接到 $y$ 上。这样，势能增加的节点仅有 $x$ （从树根变成非树根）， $y$ （秩可能增加）和操作前 $y$ 的子节点（父节点的秩可能增加）。我们先证明操作前 $y$ 的子节点 $c$ 的势能不可能增加，并且如果减少了，至少减少 $1$ 。

设操作前 $c$ 的势能为 $Φ (c)$ ，操作后为 $Φ (c^{'})$ ，这里 $c$ 可以是任意一个 $r n k (c) > 0$ 的非根节点，操作可以是任意操作，包括下面的 find 操作。我们分三种情况讨论。

$i t e r (c)$ 和 $l e v e l (c)$ 并未增加。显然有 $Φ (c) = Φ (c^{'})$ 。
$i t e r (c)$ 增加了， $l e v e l (c)$ 并未增加。这里 $i t e r (c)$ 至少增加一，即 $Φ (c^{'}) \leq Φ (c) - 1$ ，势能函数减少了，并且至少减少 1。
$l e v e l (c)$ 增加了， $i t e r (c)$ 可能减少。但是由于 $0 < i t e r (c) \leq r n k (c)$ ， $i t e r (c)$ 最多减少 $r n k (c) - 1$ ，而 $l e v e l (c)$ 至少增加 $1$ 。由定义 $Φ (c) = (α (n) - l e v e l (c)) \times r n k (c) - i t e r (c)$ ，可得 $Φ (c^{'}) \leq Φ (c) - 1$ 。
其他情况。由于 $r n k (c)$ 不变， $r n k (f a (c))$ 不减，所以不存在。

所以，势能增加的节点仅可能是 $x$ 或 $y$ 。而 $x$ 从树根变成了非树根，如果 $r n k (x) = 0$ ，则一直有 $Φ (x) = Φ (x^{'}) = 0$ 。否则，一定有 $α (x) \times r n k (x) \geq (α (n) - l e v e l (x)) \times r n k (x) - i t e r (x)$ 。即， $Φ (x^{'}) \leq Φ (x)$ 。

因此，唯一势能可能增加的点就是 $y$ 。而 $y$ 的势能最多增加 $α (n)$ 。因此，可得 $u n i o n$ 操作均摊后的时间复杂度为 $Θ (α (n))$ 。

find(a) 操作

如果查找路径包含 $Θ (s)$ 个节点，显然其查找的时间复杂度是 $Θ (s)$ 。如果由于查找操作，没有节点的势能增加，且至少有 $s - α (n)$ 个节点的势能至少减少 $1$ ，就可以证明 $f i n d (a)$ 操作的时间复杂度为 $Θ (α (n))$ 。为了避免混淆，这里用 $a$ 作为参数，而出现的 $x$ 都是泛指某一个并查集内的结点。

首先证明没有节点的势能增加。很显然，我们在上面证明过所有非根节点的势能不增，而根节点的 $r n k$ 没有改变，所以没有节点的势能增加。

接下来证明至少有 $s - α (n)$ 个节点的势能至少减少 $1$ 。我们上面证明过了，如果 $l e v e l (x)$ 或者 $i t e r (x)$ 有改变的话，它们的势能至少减少 $1$ 。所以，只需要证明至少有 $s - α (n)$ 个节点的 $l e v e l (x)$ 或者 $i t e r (x)$ 有改变即可。

回忆一下非根节点势能的定义， $Φ (x) = (α (n) - l e v e l (x)) \times r n k (x) - i t e r (x)$ ，而 $l e v e l (x)$ 和 $i t e r (x)$ 是使 $r n k (f a (x)) \geq A_{l e v e l (x)}^{i t e r (x)} (r n k (x))$ 的最大数。

所以，如果 $r o o t_{x}$ 代表 $x$ 所处的树的根节点，只需要证明 $r n k (r o o t_{x}) \geq A_{l e v e l (x)}^{i t e r (x) + 1} (r n k (x))$ 就好了。根据 $A_{k}^{i}$ 的定义， $A_{l e v e l (x)}^{i t e r (x) + 1} (r n k (x)) = A_{l e v e l (x)} (A_{l e v e l (x)}^{i t e r (x)} (r n k (x)))$ 。

注意，我们可能会用 $k (x)$ 代表 $l e v e l (x)$ ， $i (x)$ 代表 $i t e r (x)$ 以避免式子过于冗长。这里，就是 $r n k (r o o t_{x}) \geq A_{k (x)} (A_{k (x)}^{i (x)} (x))$ 。

当你看到这的时候，可能会有一种「这啥玩意」的感觉。这意味着你可能需要多看几遍，或者跳过一些内容以后再看。

这里，我们需要一个外接的 $A_{k (x)}$ ，意味着我们可能需要再找一个点 $y$ 。令 $y$ 是搜索路径上在 $x$ 之后的满足 $k (y) = k (x)$ 的点，这里「搜索路径之后」相当于「是 $x$ 的祖先」。显然，不是每一个 $x$ 都有这样一个 $y$ 。很容易证明，没有这样的 $y$ 的 $x$ 不超过 $α (n) + 2$ 个。因为只有每个 $k$ 的最后一个 $x$ 和 $a$ 以及 $r o o t_{a}$ 没有这样的 $y$ 。

我们再强调一遍 $f a (x)$ 指的是路径压缩之前 $x$ 的父节点，路径压缩之后 $x$ 的父节点一律用 $r o o t_{x}$ 表示。对于每个存在 $y$ 的 $x$ ，总是有 $r n k (y) \geq r n k (f a (x))$ 。同时，我们有 $r n k (f a (x)) \geq A_{k (x)}^{i (x)} (r n k (x))$ 。由于 $k (x) = k (y)$ ，我们用 $k$ 来统称，即， $r n k (f a (x)) \geq A_{k}^{i (x)} (r n k (x))$ 。我们需要造一个 $A_{k}$ 出来，所以我们可以不关注 $i t e r (y)$ 的值，直接使用弱化版的 $r n k (f a (y)) \geq A_{k} (r n k (y))$ 。

如果我们将不等式组合起来，神奇的事情就发生了。我们发现， $r n k (f a (y)) \geq A_{k}^{i (x) + 1} (r n k (x))$ 。也就是说，为了从 $r n k (x)$ 迭代到 $r n k (f a (y))$ ，至少可以迭代 $A_{k}$ 不少于 $i (x) + 1$ 次而不超过 $r n k (f a (y))$ 。

显然，有 $r n k (r o o t_{y}) \geq r n k (f a (y))$ ，且 $r n k (x)$ 在路径压缩时不变。因此，我们可以得到 $r n k (r o o t_{x}) \geq A_{k}^{i (x) + 1} (r n k (x))$ ，也就是说 $i t e r (x)$ 的值至少增加 1，如果 $r n k (x)$ 没有增加，一定是 $l e v e l (x)$ 增加了。

所以， $Φ (x)$ 至少减少了 1。由于这样的 $x$ 节点至少有 $s - α (n) - 2$ 个，所以最后 $Φ (S)$ 至少减少了 $s - α (n) - 2$ ，均摊后的时间复杂度即为 $Θ (α (n) + 2) = Θ (α (n))$ 。

为何并查集会被卡

这个问题也就是问，如果我们不按秩合并，会有哪些性质被破坏，导致并查集的时间复杂度不能保证为 $Θ (m α (n))$ 。

如果我们在合并的时候， $r n k$ 较大的合并到了 $r n k$ 较小的节点上面，我们就将那个 $r n k$ 较小的节点的 $r n k$ 值设为另一个节点的 $r n k$ 值加一。这样，我们就能保证 $r n k (f a (x)) \geq r n k (x) + 1$ ，从而不会出现类似于满地 compile error 一样的性质不符合。

显然，如果这样子的话，我们破坏的就是 $u n i o n (x, y)$ 函数「y 的势能最多增加 $α (n)$ 」这一句。

存在一个能使路径压缩并查集时间复杂度降至 $Ω (m \log_{1 + \frac{m}{n}} n)$ 的结构，定义如下：

二项树（实际上和一般的二项树不太一样），其中 j 是常数， $T_{k}$ 为一个 $T_{k - 1}$ 加上一个 $T_{k - j}$ 作为根节点的儿子。

二项树

边界条件， $T_{1}$ 到 $T_{j}$ 都是一个单独的点。

令 $r n k (T_{k}) = r_{k}$ ，这里我们有 $r_{k} = (k - 1) / j$ （证明略）。每轮操作，我们将它接到一个单节点上，然后查询底部的 $j$ 个节点。也就是说，我们接到单节点上的时候，单节点的势能提高了 $(k - 1) / j + 1$ 。在 $j = ⌊ \frac{m}{n} ⌋$ ， $i = ⌊ \log_{j + 1} \frac{n}{2} ⌋$ ， $k = i j$ 的时候，势能增加量为：

α (n) \times ((i j - 1) / j + 1) = α (n) \times ((⌊ \log_{⌊ \frac{m}{n} ⌋ + 1} \frac{n}{2} ⌋ \times ⌊ \frac{m}{n} ⌋ - 1) / ⌊ \frac{m}{n} ⌋ + 1)

变换一下，去掉所有的取整符号，就可以得出，势能增加量 $\geq α (n) \times (\log_{1 + \frac{m}{n}} n - \frac{n}{m})$ ，m 次操作就是 $Ω (m \log_{1 + \frac{m}{n}} n - n) = Ω (m \log_{1 + \frac{m}{n}} n)$ 。

关于启发式合并

由于按秩合并比启发式合并难写，所以很多 dalao 会选择使用启发式合并来写并查集。具体来说，则是对每个根都维护一个 $s i z e (x)$ ，每次将 $s i z e$ 小的合并到大的上面。

所以，启发式合并会不会被卡？

首先，可以从秩参与证明的性质来说明。如果 $s i z e$ 可以代替 $r n k$ 的地位，则可以使用启发式合并。快速总结一下，秩参与证明的性质有以下三条：

每次合并，最多有一个节点的秩上升，而且最多上升 1。
总有 $r n k (f a (x)) \geq r n k (x) + 1$ 。
节点的秩不减。

关于第二条和第三条， $s i z$ 显然满足，然而第一条不满足，如果将 $x$ 合并到 $y$ 上面，则 $s i z (y)$ 会增大 $s i z (x)$ 那么多。

所以，可以考虑使用 $\log_{2} s i z (x)$ 代替 $r n k (x)$ 。

关于第一条性质，由于节点的 $s i z$ 最多翻倍，所以 $\log_{2} s i z (x)$ 最多上升 1。关于第二三条性质，结论较为显然，这里略去证明。

所以说，如果不想写按秩合并，就写启发式合并好了，时间复杂度仍旧是 $Θ (m α (n))$ 。

本页面最近更新：2025/5/24 12:24:08，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：orzAtalod, Enter-tainer, H-J-Granger, StudyingFather, CCXXXI, Friendseeker, iamtwz, NachtgeistW, R-fzx, Xeonacid, yusancky
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用