并查集的时间复杂度

time_keeper · 2025-02-15 11:59:34 · 算法·理论

并查集的时间复杂度

秩的定义

我们定义一个节点的 \text{rank} 为它的秩。

有：

• 如果 x 没有子节点，\text{rank}(x) = 0。

• 否则，\text{rank}(x) = \max_{y \in son(x)}\text{rank}(y) + 1。

显然一条到根的链上的点的 \text{rank} 单调递增。

只有在合并时，根节点的 \text{rank} 才可能增加，并且根据按秩合并，至多增加 1。

我们不难看出，\text{rank} 其实是子树深度，也就是查询的复杂度。

默认并查集用了按秩合并。

引理1

对于任意 find 操作形成的图 G，|G| = n，对于他们的 \text{rank} 组成的集合 r = {1,2,3...n} ,总是有 \text{rank} = x 的元素个数不超过 \dfrac{n}{2^x}。

证明

猜想 1

发现如果两个点的 \text{rank} 相同，则两个点的子树没有重合部分。

考虑反证法，如果两个 \text{rank} 相同的点 x,y 存在重合部分 z，则存在一条路径 x\to z \to y ，那么可以得出 x,y 之间有一个是另一个的祖先，所以不会有 \text{rank} 相同。

猜想 2

对于 \text{rank} = x 的点，其子树大小至少为 2^x。

考虑数学归纳法。

有 \text{rank} = 0,size = 0。

inductive step：

假设 \text{rank} = k 成立，在合并时有两种情况：

• 两颗子树大小相同，此时新根节点的 \text{rank} + 1。

• 两颗子树大小不同，次数新根节点的 \text{rank} 不变。

合并前两颗子树的 \text{size} 均不小于 2^k，则合并后新根的 \text{rank} = k + 1 时，\text{size} \ge 2^k + 2^k \ge 2^{k + 1}。

有上面两个结论，我们假设每个 \text{rank} = x 的子树大小为 sz，由 猜想2 易得 sz \ge 2^x。

我们两边取一个倒数在同时乘 n 不难得到：

\dfrac{n}{sz}\le\dfrac{n}{2^x}

式子左边就是 \text{rank} = x 至多的元素数量，于是引理得证。

按秩合并复杂度

根据这个引理，我们可以推导出按秩合并的时间复杂度。

我们有：

令最大的 \text{rank} = x。

即 x \le \log n 所以查询操作的最大复杂度即为 \log n。

复杂度 O(m \log n)。

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

我们先定义一个函数 \text{ackermann}。

也就是：

反 \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 是坏点，当且仅当满足：

• 这个点不是根节点，且它的父亲不是根节点。

• 这个点存在祖先 y 使得 \delta(x) = \delta(y)。

反之即为好点。

在一个点 x 到根的路径上，会经过的点有下面几种：

• 一个 \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、

那么不难发现，有下面不等式：