【算法证明五】并查集的时间复杂度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法证明五】并查集的时间复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

相信如果不是为了刷 leetcode 外，很少有数据结构的数介绍并查集这一数据结构的。并查集的算法模板写起来非常容易，所以刷了并查集相关算法题的人，应该也不会去深入分析这一数据结构，最多知道路径压缩、按秩合并可以做到非常快。深入一点知道 $阿克曼函数\alpha(n)$ 就很不错了。
一般的分析方法，很难分析并查集这一数据结构的复杂度。并查集本质是一种森林，更确切的说是一种图论算法。如果不知道方法，分析这类数据结构与算法的复杂度是很难的，很容易让思维陷入困局，无法入手。分析这种算法的常用方式就是摊还分析。

数据结构接口定义

定义一组集合: $S_1,S_2...,S_k$ 和一组元素 $e_1,e_2...e_n$ ，某一个元素在同一时刻只能属于一个集合，即集合之间是不相交的。
再定义三个接口：

$M ak e (e) 用元素 e 开一个集合$
$Union(S_1, S_2)将两个集合合并$
$F in d (e) 返回元素 e 所属的集合$

其实现可以随意，但通常用集合内的某一个元素来代指一个集合。以上便是并查集数据结构的抽象定义。实际应用中，就是以上三个接口的操作序列:
$< M ak e, M ak e, ...., U ni o n, ..., F in d, ..., U ni o n, .., F in d >$
通常是 $mak e$ 在前， $U ni o n$ 、 $F in d$ 在后杂乱的形成一组操作序列。所以该数据结构的复杂度分析，就是分析这一组序列的总代价和平均代价。这就是也摊还分析技术出场的地方了。首先我们设初始元素个数为 $n$ ，操作序列的长度为 $m$ 。显然 $\ge n$

链表实现

用链表来实现该数据结构是比较简单的。集合结构包含一个链表头节点和尾节点。每一个链表节点表示集合中的一个元素。链表节点中包含一个next指向下一个链表，包含一个 S 指针指向属于的集合节后。
在上面的定义链表实现中， $mak e$ 操作和 $F in d$ 操作都是 $O (1)$ 的。核心在于 $U ni o n$ 操作。简单的 $U ni o n$ 操作就是把S_2中的所有元素的S指针指向S_1。将S_2的链表插入S_1中。这样， $U ni o n$ 操作的复杂度为跟S_2的链表长度有关。容易想到，这种方法的最坏情况就是将n个集合依次合并的情况。总复杂度为 $\sum_1^ni=\Theta(n^2)$ ，每个操作摊还复杂度为 $\Theta(n)$ 。

加权合并策略

上面最坏情况的构造，是基于每次将最长的集合，合并入短的集合内。如果加一种启发式策略，每次判断一下，将较短的集合，合并入较长的集合内，算法又该如何分析呢？还是只考虑复杂情况 $U ni o n$ 的复杂度变化。首先，我们最多执行Union操作n-1次。我们不妨考虑更底层的情况：考虑任意一个元素e的S指针被更新的次数。
由于我们采用将较小集合的S指针更新，因此第一次e被更新后，其所在集合中元素的数量一定 $\ge2$ 。下依次e被更新后，其所在集合中的元素数量一定 $\ge4$ 。当e所在的集合数量 $\ge n/2$ 时，e的S指针将不再更新，故每个e的S指针最多被更新 $l g n$ 次。所以n-1次Union操作的总代价应 $\le nlgn$ 。所以序列的最坏情况下总代价为 $O (m + n l g n)$ 。摊还复杂度，最坏情况下为 $O (l g n)$ 。

看，其实用看起来不怎么好的链表实现加上简单的加权合并，并查集的摊还复杂度就已经来到 $O (l g n)$ 了。

森林实现

森林实现就是我们常见的刷题模板了

// Make
int p[MAX_N], r[MAX_N];
for (int i = 0; i < n; i++) p[i] = i;

int find(int i) { 
	// 不带路径压缩
	while(p[i] != i)
		i = p[i];
	return i;
	// 路径压缩
	// return p[i] == i ? i : p[i] = find(p[i]);
}

void union(int x, int y) {
	x = find(x);
	y = find(y))
	if(r[x] > r[y]) 
		p[y] = x;
	else {
		p[x]=y;
		if (r[x]==r[y]) r[y]++;
	}
}

如果将 r 数组想象成链表实现中的秩的话，其证明过程是类似的，可以得到，按秩合并产生的运行时间为O(mlgn)。但是find操作要慢一些，不过可以分析其最坏情况就是在序列的最后，find 树中最深的元素，所以也是O(mlgn)的。所以单独使用按秩合并，最坏情况下摊还复杂度还是 $O (l g n)$ 。

优化最好的路径压缩。这里并不打算证明(以后再说)，只给出结论：当使用路径压缩时，长度为m的序列操作的总代价是 $O(m\alpha(n))$ 。 $\alpha(n)$ 函数是增长非常慢的一种函数，当 $\le n\le16^{512}$ 是， $\alpha(n)$ 仅为4。所以在实际应用中当作 $O (1)$ 也无妨。因此摊还代价为 $O (1)$

重要的是理解摊还分析的建模和分析思路：即定义一组操作序列，从整体的角度出发，计算所有操作的代价总和。例如，我们这里并没有直接计算 $U ni o n$ 操作的最坏复杂度，而是从一个元素被更新所属集合的次数出发，求得了代价总和。文章来源地址https://www.toymoban.com/news/detail-502286.html

到了这里，关于【算法证明五】并查集的时间复杂度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！