分析并查集算法的时间复杂度？

Question

请简要说明分析并查集算法时间复杂度的方法，包括两种情况： 1. 标准方法 2. 加权并查集启发式方法

我知道在标准版本中，其时间复杂度为：O(n^2)，而在加权并查集启发式方法中，其时间复杂度为：O(m + n logn)。

但我不明白它是如何推导出来的。 假设：考虑有n个元素和链表数据结构，每个节点都指向列表头部，m表示进行集合操作的次数。

- Sonali

---

请查看Robert Sedgewick/Kevin Wayne的《算法》（第四版）书籍。第1.5节。 - Abhishek Bansal

http://algs4.cs.princeton.edu/15uf/ - Abhishek Bansal

@Abhishek Bansal，您提供的链接没有分析算法。 - Sonali

Answer 1

首先定义一些术语：m 是 make-set 操作的次数，n 是 union/find 操作的总次数。

标准版本

假设 join(a,b) 将 b 设为 a 的根节点。

如果有一个调用序列包括 0.5n 次调用，如 joint(1,2)、joint(2,3) 和 joint(3,4)，你可以用 1 作为底部连接 0.5n 个节点。然后，find(1) 将花费 0.5n 的时间，所以将其调用 0.5n 次，运行时间将为 0.25n^2=O(n^2)。

由于我们必须执行 m 次 makeset 操作，因此最终的时间复杂度为 O(m+n^2)。

加权并查集

我假设集合的大小是权重（而不是等级）。

对于给定的集合，设 h 为表示它的树的高度，w 为其大小。在该集合中，find 最多需要 h 的时间。通过归纳法，我们可以证明 h<=log(w)。

对于一个只有一个节点的树，其 w=1 且 h=0，公式显然成立。

现在考虑两棵树a和b之间的连接，其中a成为新的根。假设a和b满足h<=log(w)，我们将证明它对于联合也成立。我们知道wa>=wb => wab = wa+wb >= 2wb。如果a比b高，那么我们有hab = ha <= log(wa) <= log(wab)。否则（当hb >= ha时），我们有hab = 1+hb <= 1+log(wb) = log(2wb) <= log(wab)。

这证明了h<=log(w)成立。换句话说，我们已经证明了任何集合的高度都小于其大小的对数，因此查找最多需要O(log(k))时间，其中k是集合的大小。

设j为联合操作的数量。每个union操作涉及2个元素，因此任何集合的最大大小受到2j的限制。

因此，联合和查找的运行时间为O(j+k log(2j)) = O(n + n log(2n)) = O(n log(n))。同样，我们必须进行m个makeset操作，因此总共得到O(m + n log(n))

- Tobber

---

什么是 make-set 操作？ - cosmos