从理论分析并查集的时间复杂度

· · 算法·理论

本篇文章同步发在我的github博客

并查集的时间复杂度

其实自从高二开始学习并查集就发现这个数据结构真的奇妙,能解决许多问题,但是对时间复杂度就不太理解,大二退役之后我开始想去知道为什么是这个奇妙的时间复杂度,遂有此文。

本文参考了:OI-Wiki,coursera上的算法课程

这里证明并没有引入势能分析,但是相关东西异曲同工。

引入

并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。

并查集支持两种操作:

朴素算法

查询:我们需要沿着树向上移动,直至找到根节点。

合并:要合并两棵树,我们只需要将一棵树的根节点连到另一棵树的根节点。

那么这样的时间复杂度有多少呢?

排名(Rank)

对于并查集的中的每个树,其中 V 是节点集合,E 是边集合,r 为树的子节点,对于任意节点 v \in V,定义节点 v 的排名 \text{rank} 为:

某个节点到根结点的路径上的边数的最大值为排名(Rank)

注意:下面所有秩都和 \text{rank} 一个意思

那么就有以下性质:

  1. 对于任意节点 x\text{rank}(x) 只会增加
  2. 在合并时,只有根节点的 \text{rank}(x) 才有可能增加
  3. 在一条路径(从下至上)中 \text{rank}(x) 严格递增

rank 的引理 1

对于任意的查询Find操作,该操作中生成的图 G|G| = n,对于所有的 r \in \{1,2,3 \dots n\}\text{rank} = r 的元素个数 \leq \frac{n}{2^r}

证明引理 1
  1. 假设一:如果两个的不相同的点的 \text{rank} 相同,那么他们的子树不可能有重合部分。

    • 反证:如果有重合部分,那么一定有一个路径 x\to z \to yz 为重合部分,x,y 为两个 rank 相同的点,那么可以得出 xy 之间有更大的祖先,那么就有更大的 \text{rank},与假设不符。
  2. 假设二:\text{rank}=x 的子树的元素 \ge 2^n(数学归纳法)

证明:Base\text{rank} = 0,size =0

inductive step

  1. 不一样的子树大小,\text{rank} 不变

  2. 一样的子树大小, \text{rank} + 1

X_s = 合并前一个子树的大小 \geq 2^r,Y_s = 合并前另一个子树的大小 \geq 2^r

合并后,Union(x,y)得到了新祖先 Z\text{rank}(z) = r+1

现在我们来证明引理 1:n 个元素,我们设**每个** $\text{rank}=x$ 的子树的大小为 $x$,假设二可知,$x \geq 2^r

我们两边取倒数,并且同时乘一个 n,那么可以得出 \dfrac{n}{x} \leq \dfrac{n}{2^r},那么可以看出左边就是 \text{rank} = r 的元素个数,引理 1 也证明完毕了。

时间复杂度

证明了这么多,我们也能看出来 \text{rank} 其实就是一个子树的深度,也是我们最多要查询的次数。

首先,最大\text{rank}的个数=祖先的个数=1,显然,那么根据引理1,得出:

1 \leq \frac{n}{2^r} \ \Rightarrow 2^r \leq n \Rightarrow r \leq \log_{2}n

那么我们可以得到查询和合并的时间复杂度为 O(\log_{2} n)

路径压缩+启发式合并(按秩合并)

上面的朴素算法已经很快了,但是考虑一种可能,如果这个不是一个正常的树,而是一条链,而我们正常的去查询最底下的节点,那么复杂度将会退化成 O(n),这并不是我们想要的,想到我们查询时有许多地方时冗余的,我们就想到了路径压缩。

路径压缩:查询过程中经过的每个元素都属于该集合,我们可以将其直接连到根节点以加快后续查询。

在合并时我们又想到了这两个的 \text{rank} 不同也会导致路径压缩的时候会多了一些不该有的操作。

启发式合并(按秩合并):合并时,选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵,以免发生退化。

另一种做法则是使用“秩”来比较树的大小。”秩“的定义如下:

容易发现,在没有路径压缩优化时,树的秩等于树的深度减一。在有路径压缩优化时,树的秩仍然能反映出树的深度和大小。在合并时根据两棵树的秩的大小,决定新的根节点,这被称作按秩合并

Theorem

注意:经过路径压缩过时,\text{rank} 不变,相当于被冻结了,不管压缩到哪都不会改变

内容:通过“按秩合并”和“路径压缩”优化后,进行 m 次合并+查询的操作的时间复杂度为 O(m \log^* n),其中 \log^* n 表示对 n 反复应用对数运算,直到结果小于等于 1 所需要的次数,一般叫迭代对数。

x \lg^* x
(−\infty, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 2^{65536}] 5

证明

首先我们来定义一个 \text{rank\, blocks}(秩块);\{0\},\{1\},\{2,3,4\},\{5,\dots, 2 4 \},\{17,18,\dots,2^{16}\}, \{65537,\dots,2^{65536}\},\dots,\{\dots,n\}

很显然这些块只会有 O(\log^* n) 个。

我们给每个节点分类,我们现在称一个节点 x(可变)是好的当:

  1. 父亲的 \text{rank} 比自己的 \text{rank} 大。 注意:\text{rank} 不变

如果两个条件都不符合,那么就是坏节点。

我们会尽量将一个节点变成好节点。

第一个要点:要点:每次查找操作只会访问 O(\log^* n) 个好节点 (计算方式为 2 + 秩块的数量 = O(\log^* n)

结论:在 m 次操作中完成的总工作量可以表示为两种:

首先我们思考,在路径压缩中,其父节点被更改为具有严格更大 \text{rank} 的节点,这种情况最多只会发生 2^k 次,之后 x 将永久成为“好节点”。(很显然,在路径压缩中,那个节点相当于在往上跳,最多跳到这个 block 的第一个)

总时间复杂度:O(m \log^* n) + O(访问坏节点的次数)

我们对一个秩块 \{k+1, k+2, \dots, 2^k\} 分析:

对于每个最终秩处于此块的 x,当 x 是“坏节点”时的访问次数最多为 2^k

具有最终 \text{rank} 处于此块的对象总数为:

\sum_{i=k+1}^{2^k} \frac{n}{2^i} \leq \frac{n}{2^k}

因此,此秩块中对“坏节点”的访问总次数最多为 n

因为只有 O(\log^* n) 个秩块。

总时间复杂度

### Tarjan’s Bound 该证明在1975年由Tarjan完成,后在1989年,由Fredman证明该结构下无法找到更好的时间复杂度 **内容**:通过“按秩合并”和“路径压缩”优化后,进行 $m$ 次合并和查找操作的时间复杂度为 $O(m \alpha(n))$,其中 $\alpha(n)$ 是反阿克曼函数。 #### 阿克曼函数 需要两个自然数作为输入值,输出一个自然数,它的输出值增长速度非常高。 定义: $$ A(m,n) = \begin{cases}n + 1 & \text{如果 m=0} \\ A(m-1,1) & \text{如果 m>0 且 n=0} \\ A(m-1,A(m,n-1)) & \text{如果 m>0 且 n>0 }\end{cases} $$ 由于这个函数的增加速率非常快,那么它的反函数就相应的增长的非常慢。 **反函数的定义**:对于每个 $n \geq 4$,$\alpha(n)$ 是满足 $A_k(2) \geq n$ 的最小 $k$ 值,其中 $A_k(2)$ 是阿克曼函数。 > $\alpha(n) = 1 \Rightarrow n=4
\alpha(n) = 2 \Rightarrow n=5 \dots 8 \alpha(n) = 3 \Rightarrow n=9 ,10\dots 2048 \alpha(n) = 4 \Rightarrow n=4\dots n(n 满足 \log^*n= 2048) \cdots

证明

我们定义 x 为不是根节点 \delta(x) 是最大的 k 使得 \text{rank}(\text{parent}[x]) \geq A_k(\text{rank}(x))

显然, \delta(x) 是递增的。

这里有一个性质:只要 \text{rank} \geq 2 的点,那么一定会有 \delta(x) \leq \alpha(n)

证明:

A_{\alpha(n)}(2) \geq n \geq \text{rank}(parent[x]) \geq A_k(\text{rank}(x))

其中 n \geq \text{rank}(parent[x]) 很显然一定成立,左边其实就是上面反函数的定义,右边就是 \delta(x) 的定义,最左边与最右边分别进行反函数,即证成立。

这里我们继续定义好节点与坏节点:

一个点为好的节点当且仅当符合下面几个条件,我们称这个节点为坏节点:

  1. 它的父亲不是根节点
  2. \text{rank}(x) \geq 2
  3. x$ 存在祖先 $y$ 使得 $\delta(y) = \delta(x)

否则,x 是好的节点。

同 Hopcroft-Ullman 类似,在一次路径中最多有 \Theta(\alpha(n)) \leq 2 +2 +\alpha(n) 个好节点。

那么最终 m 次操作(合并与查询)的总时间复杂度:O(m\alpha(n))(访问好节点的次数)+访问坏节点的次数

下面我们来计算一下这个坏节点的个数,我们同样只先看一次路径的:

路径压缩:p'x 的新父亲或者更向上,则有:

\text{rank}(x的新父亲) \geq \text{rank}(p') \geq A_k(\text{rank}(y)) \geq A_k(\text{rank}(p))

中间这个过渡我们用到了上面 \delta(x) 的定义,其他的都很显然。

假设 r = \text{rank}(x),然后我们对 xr 次查找(路径压缩),假设每次都是有用的,那么我的 \delta(x) 至少 +1

为什么?我们不从理性的(数学的)角度去分析,而是去从感性的角度,首先想 \text{rank}(x) = 0,1,显然根据定义,本身就是好节点,成立。

那么 \text{rank}(x) \geq 2 呢?压缩一次会压缩到好节点的同地方,下一次必然会压缩到下一个 \delta(x) + 1 中,所以的证,而且是至少

那最多可以加多少次 1 呢?\alpha(n)

那么 x 是坏的 \leq r \alpha(n)

那么我们开始算总共访问坏节点的次数:

\begin{align*} &总共访问坏节点的次数 \\ &\leq \Sigma_{所有节点}\text{rank}(x) \cdot \alpha(n) \tag 1\\ &= \alpha(n) \cdot \Sigma_{r \geq 0} \,r \,(\text{rank}=r 节点的个数) \tag2\\ &\leq n \alpha(n) \Sigma_{r \geq 0} \frac{r}{2^r} \tag 3\\ &= O(n \alpha(n)) \end{align*}

我们来解释一下这个东西怎么来的,在 (2) \to (3) 中的推导中我们用到了 rank 的引理 1,不理解的可以倒回去看看,这里我们对每个 r 都用了一个引理 1 并相加,(3) 中的 \Sigma_{r \geq 0} \frac{r}{2^r},其实是个几何级数,最后是个常数,可以省略,就得到了坏节点的次数。

那么我们能得出总共的时间复杂度为: