首先定义一些术语: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))