并查集时间复杂度证明

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

这里,先给出 \alpha(n) 的定义。为了给出这个定义,先给出 A_k(j) 的定义。

定义 A_k(j) 为:

A_k(j)=\left\{ \begin{aligned} &j+1& &k=0&\\ &A_{k-1}^{(j+1)}(j)& &k\geq1& \end{aligned} \right.

即阿克曼函数。

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

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

基础定义

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

为了定义势函数,需要预先定义一个辅助函数 level(x) 。其中, level(x)=\max(k:rnk(fa(x))\geq A_k(rnk(x))) 。当 rnk(x)\geq1 的时候,再定义一个辅助函数 iter(x)=\max(i:rnk(fa(x))\geq A_{level(x)}^i(rnk(x)) 。这些函数定义的 x 都满足 rnk(x)>0 x 不是某个树的根。

上面那些定义可能让你有点头晕。再理一下,对于一个 x fa(x) ,如果 rnk(x)>0 ,总是可以找到一对 i,k rnk(fa(x))\geq A_k^i(rnk(x)) ,而 level(x)=\max(k) ,在这个前提下, iter(x)=\max(i) level 描述了 A 的最大迭代级数,而 iter 描述了在最大迭代级数时的最大迭代次数。

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

0\leq level(x)<\alpha(n)
1\leq iter(x)\leq rnk(x)

考虑 level(x) iter(x) A_k^j 的定义,这些很容易被证明出来,就留给读者用于熟悉定义了。

定义势能函数 \Phi(S)=\sum\limits_{x\in S}\Phi(x) ,其中 S 表示一整个并查集,而 x 为并查集中的一个节点。定义 \Phi(x) 为:

\Phi(x)=\left\{ \begin{aligned} &\alpha(n)\times rnk(x)& &rnk(x)=0\text{ 或 x为某棵树的根节点}&\\ &(\alpha(n)-level(x))\times rnk(x)-iter(x)& &otherwise& \end{aligned}\right.

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

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

union(x,y) 操作

其花费的时间为 \Theta(1) ,因此我们考虑其引起的势能的变化。

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

设操作前 c 的势能为 \Phi(c) ,操作后为 \Phi(c') ,这里 c 可以是任意一个 rnk(c)>0 的非根节点,操作可以是任意操作,包括下面的 find 操作。我们分三种情况讨论。

  1. iter(c) level(c) 并未增加。显然有 \Phi(c)=\Phi(c')
  2. iter(c) 增加了, level(c) 并未增加。这里 iter(c) 至少增加一,即 \Phi(c')\leq \Phi(c)-1 ,势能函数减少了,并且至少减少 1。
  3. level(c) 增加了, iter(c) 可能减少。但是由于 0<iter(c)\leq rnk(c) iter(c) 最多减少 rnk(c)-1 ,而 level(c) 至少增加 1 。由定义 \Phi(c)=(\alpha(n)-level(c))\times rnk(c)-iter(c) ,可得 \Phi(c')\leq\Phi(c)-1
  4. 其他情况。由于 rnk(c) 不变, rnk(fa(c)) 不减,所以不存在。

所以,势能增加的节点仅可能是 x y 。而 x 从树根变成了非树根,如果 rnk(x)=0 ,则一直有 \Phi(x)=\Phi(x')=0 。否则,一定有 \alpha(x)\times rnk(x)\geq(\alpha(n)-level(x))\times rnk(x)-iter(x) 。即, \Phi(x')\leq \Phi(x)

因此,唯一势能可能增加的点就是 y 。而 y 的势能最多增加 \alpha(n) 。因此,可得 union 操作均摊后的时间复杂度为 \Theta(\alpha(n))

find(a) 操作

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

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

接下来证明至少有 s-\alpha(n) 个节点的势能至少减少 1 。我们上面证明过了,如果 level(x) 或者 iter(x) 有改变的话,它们的势能至少减少 1 。所以,只需要证明至少有 s-\alpha(n) 个节点的 level(x) 或者 iter(x) 有改变即可。

回忆一下非根节点势能的定义, \Phi(x)=(\alpha(n)-level(x))\times rnk(x)-iter(x) ,而 level(x) iter(x) 是使 rnk(fa(x))\geq A_{level(x)}^{iter(x)}(rnk(x)) 的最大数。

所以,如果 root_x 代表 x 所处的树的根节点,只需要证明 rnk(root_x)\geq A_{level(x)}^{iter(x)+1}(rnk(x)) 就好了。根据 A_k^i 的定义, A_{level(x)}^{iter(x)+1}(rnk(x))=A_{level(x)}(A_{level(x)}^{iter(x)}(rnk(x)))

注意,我们可能会用 k(x) 代表 level(x) i(x) 代表 iter(x) 以避免式子过于冗长。这里,就是 rnk(root_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 不超过 \alpha(n)-2 个。因为只有每个 k 的最后一个 x a 以及 root_a 没有这样的 y

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

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

显然,有 rnk(root_y)\geq rnk(fa(y)) ,且 rnk(x) 在路径压缩时不变。因此,我们可以得到 rnk(root_x)\geq A_k^{i(x)+1}(rnk(x)) ,也就是说 iter(x) 的值至少增加 1,如果 rnk(x) 没有增加,一定是 level(x) 增加了。

所以, \Phi(x) 至少减少了 1。由于这样的 x 节点至少有 s-\alpha(n)-2 个,所以最后 \Phi(S) 至少减少了 s-\alpha(n)-2 ,均摊后的时间复杂度即为 \Theta(\alpha(n)+2)=\Theta(\alpha(n))

为何并查集会被卡

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

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

显然,如果这样子的话,我们破坏的就是 union(x,y) 函数「y 的势能最多增加 \alpha(n) 」这一句。

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

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

我们的二项树

边界条件, T_1 T_j 都是一个单独的点。

rnk(T_k)=r_k ,这里我们有 r_k=(k-1)/j (证明略)。每轮操作,我们将它接到一个单节点上,然后查询底部的 j 个节点。也就是说,我们接到单节点上的时候,单节点的势能提高了 (k-1)/j+1 。在 j=\lfloor\frac{m}{n}\rfloor i=\lfloor\log_{j+1}\frac{n}{2}\rfloor k=ij 的时候,势能增加量为:

\alpha(n)\times((ij-1)/j+1)=\alpha(n)\times((\lfloor\log_{\lfloor\frac{m}{n}\rfloor+1}\frac{n}{2}\rfloor\times \lfloor\frac{m}{n}\rfloor-1)/\lfloor\frac{m}{n}\rfloor+1)

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

关于启发式合并

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

所以,启发式合并会不会被卡?

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

  1. 每次合并,最多有一个节点的秩上升,而且最多上升 1。
  2. 总有 rnk(fa(x))\geq rnk(x)+1
  3. 节点的秩不减。

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

所以,可以考虑使用 \log_2 siz(x) 代替 rnk(x)

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

所以说,如果不想写按秩合并,就写启发式合并好了,时间复杂度仍旧是 \Theta(m\alpha(n))


评论