专栏文章

并查集的时间复杂度

ttime_keeper
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq92npd
此快照首次捕获于
2025/12/04 00:57
3 个月前
此快照最后确认于
2025/12/04 00:57
3 个月前
查看原文

并查集的时间复杂度

秩的定义

我们定义一个节点的 rank\text{rank} 为它的秩。
有：
  • 如果 xx 没有子节点，rank(x)=0\text{rank}(x) = 0。
  • 否则，rank(x)=max⁡y∈son(x)rank(y)+1\text{rank}(x) = \max_{y \in son(x)}\text{rank}(y) + 1。
显然一条到根的链上的点的 rank\text{rank} 单调递增。
只有在合并时，根节点的 rank\text{rank} 才可能增加，并且根据按秩合并，至多增加 11。
我们不难看出，rank\text{rank} 其实是子树深度，也就是查询的复杂度。
默认并查集用了按秩合并。
引理1
对于任意 findfind 操作形成的图 GG，∣G∣=n|G| = n，对于他们的 rank\text{rank} 组成的集合 r=1,2,3...nr = {1,2,3...n} ,总是有 rank=x\text{rank} = x 的元素个数不超过 n2x\dfrac{n}{2^x}。
证明
猜想 1
发现如果两个点的 rank\text{rank} 相同，则两个点的子树没有重合部分。
考虑反证法，如果两个 rank\text{rank} 相同的点 x,yx,y 存在重合部分 zz，则存在一条路径 x→z→yx\to z \to y ，那么可以得出 x,yx,y 之间有一个是另一个的祖先，所以不会有 rank\text{rank} 相同。
猜想 2
对于 rank=x\text{rank} = x 的点，其子树大小至少为 2x2^x。
考虑数学归纳法。
有 rank=0,size=0\text{rank} = 0,size = 0。
inductive step：
假设 rank=k\text{rank} = k 成立，在合并时有两种情况：
  • 两颗子树大小相同，此时新根节点的 rank+1\text{rank} + 1。
  • 两颗子树大小不同，次数新根节点的 rank\text{rank} 不变。
合并前两颗子树的 size\text{size} 均不小于 2k2^k，则合并后新根的 rank=k+1\text{rank} = k + 1 时，size≥2k+2k≥2k+1\text{size} \ge 2^k + 2^k \ge 2^{k + 1}。
有上面两个结论，我们假设每个 rank=x\text{rank} = x 的子树大小为 szsz，由 猜想2 易得 sz≥2xsz \ge 2^x。
我们两边取一个倒数在同时乘 nn 不难得到：
nsz≤n2x\dfrac{n}{sz}\le\dfrac{n}{2^x}
式子左边就是 rank=x\text{rank} = x 至多的元素数量，于是引理得证。

按秩合并复杂度

根据这个引理，我们可以推导出按秩合并的时间复杂度。
我们有：
令最大的 rank=x\text{rank} = x。
1≤n2x⟹2x≤n1 \le \dfrac{n}{2^x} \Longrightarrow 2^x \le n
即 x≤log⁡nx \le \log n 所以查询操作的最大复杂度即为 log⁡n\log n。
复杂度 O(mlog⁡n)O(m \log n)。

路径压缩+按秩合并复杂度

我们先定义一个函数 ackermann\text{ackermann}。
n + 1 && m = 0\\ A_{m-1}(1) && m > 0 \wedge n = 0\\ A_{m-1}(A_m(n - 1)) && m > 0 \wedge n > 0 \end{cases}$$ 也就是： $$A_m(n)=\begin{cases} n+1 && m = 0\\ A_{m-1}^{n+1}(n) && m \ge 1 \end{cases}$$ 反 $\text{ackermann}$ 即 $\alpha(x)$ 表示满足 $A_k(2) \ge x$ 的最小 $k$ 值。 > 在这里定义 $\alpha(x)$ 为 $A_k(2) \ge x$ 或者 $A_k(0) \ge x$ 都可以，$\alpha(n)$ 都是很小的。 我们令 $\delta(x)$ 表示满足 $\text{rank}(fa_x) \ge A_k(\text{rank}(x))$ 的最大 $k$ 值。 显然随着时间的推移，$\delta(x)$ 只增不减，且非负。 > 证明： > > 首先有 $\text{rank}(fa_x)\ge \text{rank}(x) +1$。 > > 则 $\delta(x)$ 一定非负。 > > 并且对于并查集来说，一个点如果现在不是根，那么以后他就都不是根了，只有根节点的 $\text{rank}$ 会变大，那么 $\delta(x)$ 只会变大，并且变大只发生在根节点的儿子上。 **性质 1** 对于的满足 $\text{rank} \ge 2$ 的点，都有 $\delta(x) \le \alpha(n)$。 >证明： > >$A_{\alpha(n)}(2) \ge n \ge \text{rank}(fa_x) \ge A_k(\text{rank}(x))$ 我们定义一个点 $x$ 是坏点，当且仅当满足： - 这个点不是根节点，且它的父亲不是根节点。 - $\text{rank}(x) \ge 2$。 - 这个点存在祖先 $y$ 使得 $\delta(x) = \delta(y)$。 反之即为好点。 在一个点 $x$ 到根的路径上，会经过的点有下面几种： - $1$ 个根节点。 - $1$ 个根节点的儿子。 - 一个 $\text{rank} = 0$ 的节点。 - 一个 $\text{rank} = 1$ 的节点。 - 对于每一个 $\text{rank} = k(k \ge 2)$ 只会经过一个好节点，并且这个好节点是路径上所有 $\delta(x) = k$ 的最靠近根的那一个节点。 > 其他的 $\delta(x) = k$ 的节点都存在一个祖先使得 $\delta(x) = \delta(y)$，是坏节点。 那么路径上经过的好节点的数量是 $2 + 2 + \alpha(n) = O(\alpha(n))$ 的。 再来统计坏节点的经过次数。 对于一个点 $x$，我们令 $r = \text{rank}(x),k = \delta(x)$。 我们对这个点做 $r$ 次路径压缩，假设这些都成功压缩了，令 $x$ 每次路径压缩完的父亲分别为 $fa_1,fa_2...fa_r$、 那么不难发现，有下面不等式： $\text{rank}(fa_r) \ge A_k(\text{rank}(fa_{r-1}))$。 我们继续对里面进行展开： $\text{rank}(fa_r)\ge A_k(A_k(\text{rank}(fa_{r-2}))$。 $\text{rank}(fa_r) \ge A_k(A_k(A_k....(r)))$。 即有： $$\text{rank}(fa_r)\ge A_{k}^{r+1}(r)$$ 看一下上面的 $\text{Ackermann}$ 定义式，我们发现这个式子的形式就是 $m>0$ 的形式。 那么也就是说 $\text{rank}(fa_r) \ge A_{k+1}(r)$。 这个不等式告诉我们，对 $x$ 成功做 $r$ 次路径压缩，它的 $\delta(x)$ 至少需要增加 $1$。 而且显然 $\delta(x)$ 最大为 $\alpha(n)$。 那么我们对一个坏点最多访问 $\text{rank}(x) \times \alpha(n)$ 次。 总共需要访问坏点的次数为： $$\sum_{u \in G \wedge S_{Bad}}\text{rank}(u) \times \alpha(n)$$ $$=\alpha(n) \times \sum_{r \ge 0}(cnt[\text{rank}(r)] \times r)$$ 由引理 1 得： $$\le n \alpha(n) \times \sum_{r \ge 0} \dfrac{r}{2^r}$$ 后面的这个式子很小，可以作为常数忽略。 那么坏点的访问次数至多为 $O(n \alpha(n))$。 再加上每次 `find` 的 $\alpha(n)$。 时间复杂度为 $O((n + m)\alpha(n))$。 通常情况下我们认为 $n,m$ 同阶，因此复杂度为 $O(n \alpha(n))$。 ------- 本文参考了 [coursera](https://www.coursera.org/lecture/algorithms-greedy/path-compression-the-hopcroft-ullman-analysis-i-advanced-optional-KdbbU) 和 [从理论分析并查集的时间复杂度](https://www.luogu.com.cn/article/o86l5jfy)。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...