并查集复杂度

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

这里，先给出的定义。为了给出这个定义，先给出的定义。

定义为：

即阿克曼函数。

这里，表示将连续应用在上次，即，。

再定义为使得的最小整数值。注意，我们之前将它描述为，反正他们的增长速度都很慢，值都不超过 4。

基础定义¶

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

为了定义势函数，需要预先定义一个辅助函数。其中，。当的时候，再定义一个辅助函数。这些函数定义的都满足且不是某个树的根。

上面那些定义可能让你有点头晕。再理一下，对于一个和，如果，总是可以找到一对令，而，在这个前提下，。描述了的最大迭代级数，而描述了在最大迭代级数时的最大迭代次数。

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

考虑、和的定义，这些很容易被证明出来，就留给读者用于熟悉定义了。

定义势能函数，其中表示一整个并查集，而为并查集中的一个节点。定义为：

然后就是通过操作引起的势能变化来证明摊还时间复杂度为啦。注意，这里我们讨论的操作保证了和都是某个树的根，因此不需要额外执行和。

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

union(x,y) 操作¶

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

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

设操作前的势能为，操作后为，这里可以是任意一个的非根节点，操作可以是任意操作，包括下面的 find 操作。我们分三种情况讨论。

和并未增加。显然有。
增加了，并未增加。这里至少增加一，即，势能函数减少了，并且至少减少 1。
增加了，可能减少。但是由于，最多减少，而至少增加。由定义，可得。
其他情况。由于不变，不减，所以不存在。

所以，势能增加的节点仅可能是或。而从树根变成了非树根，如果，则一直有。否则，一定有。即，。

因此，唯一势能可能增加的点就是。而的势能最多增加。因此，可得操作均摊后的时间复杂度为。

find(a) 操作¶

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

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

接下来证明至少有个节点的势能至少减少。我们上面证明过了，如果或者有改变的话，它们的势能至少减少。所以，只需要证明至少有个节点的或者有改变即可。

回忆一下非根节点势能的定义，，而和是使的最大数。

所以，如果代表所处的树的根节点，只需要证明就好了。根据的定义，。

注意，我们可能会用代表，代表以避免式子过于冗长。这里，就是。

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

这里，我们需要一个外接的，意味着我们可能需要再找一个点。令是搜索路径上在之后的满足的点，这里“搜索路径之后”相当于“是的祖先”。显然，不是每一个都有这样一个。很容易证明，没有这样的的不超过个。因为只有每个的最后一个和以及没有这样的。

我们再强调一遍指的是路径压缩之前的父节点，路径压缩之后的父节点一律用表示。对于每个存在的，总是有。同时，我们有。由于，我们用来统称，即，。我们需要造一个出来，所以我们可以不关注的值，直接使用弱化版的。

如果我们将不等式组合起来，神奇的事情就发生了。我们发现，。也就是说，为了从迭代到，至少可以迭代不少于次而不超过。

显然，有，且在路径压缩时不变。因此，我们可以得到，也就是说的值至少增加 1，如果没有增加，一定是增加了。

所以，至少减少了 1。由于这样的节点至少有个，所以最后至少减少了，均摊后的时间复杂度即为。

为何并查集会被卡¶

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

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

显然，如果这样子的话，我们破坏的就是函数「y 的势能最多增加」这一句。

存在一个能使路径压缩并查集时间复杂度降至的结构，定义如下：

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

我们的二项树

边界条件，到都是一个单独的点。

令，这里我们有（证明略）。每轮操作，我们将它接到一个单节点上，然后查询底部的个节点。也就是说，我们接到单节点上的时候，单节点的势能提高了。在，，的时候，势能增加量为：

变换一下，去掉所有的取整符号，就可以得出，势能增加量，m 次操作就是。

关于启发式合并¶

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

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

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

每次合并，最多有一个节点的秩上升，而且最多上升 1。
总有。
节点的秩不减。

关于第二条和第三条，显然满足，然而第一条不满足，如果将合并到上面，则会增大那么多。

所以，可以考虑使用代替。

关于第一条性质，由于节点的最多翻倍，所以最多上升 1。关于第二三条性质，结论较为显然，这里略去证明。

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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：orzAtalod
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用