跳转至

并查集复杂度

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

定义

阿克曼函数

这里,先给出 α(n) 的定义。为了给出这个定义,先给出 Ak(j) 的定义。

定义 Ak(j) 为:

Ak(j)={j+1k=0Ak1(j+1)(j)k1

即阿克曼函数。

这里,fi(x) 表示将 f 连续应用在 xi 次,即 f0(x)=xfi(x)=f(fi1(x))

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

基础定义

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

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

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

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

0level(x)<α(n) 1iter(x)rnk(x)

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

定义势能函数 Φ(S)=xSΦ(x),其中 S 表示一整个并查集,而 x 为并查集中的一个节点。定义 Φ(x) 为:

Φ(x)={α(n)×rnk(x)rnk(x)=0  x 为某棵树的根节点(α(n)level(x))×rnk(x)iter(x)otherwise

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

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

证明

union(x,y) 操作

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

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

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

  1. iter(c)level(c) 并未增加。显然有 Φ(c)=Φ(c)
  2. iter(c) 增加了,level(c) 并未增加。这里 iter(c) 至少增加一,即 Φ(c)Φ(c)1,势能函数减少了,并且至少减少 1。
  3. level(c) 增加了,iter(c) 可能减少。但是由于 $0