请给出一个简单的方法来分析联合查找算法的时间复杂度。在这两种情况下 1. 标准方法 2. 加权联合启发式方法
我知道在标准版本中，它的时间复杂度是：O(n^2) ，如果是加权联合启发式方法，它是：O(m + n logn)
但我没有得到，它是怎么来的。假设：假设有 n 个元素和链表数据结构，每个节点都指向链表的头部，m=make set 操作。
问问题
8375 次
1 回答
0
首先是一些定义：m是 make-set 操作的数量。n是联合/查找操作的总和。
标准版本
假设这join(a,b)使得.ba
如果有0.5n个调用的调用序列，如joint(1,2), joint(2,3)，joint(3,4)您可以在按钮中创建一个0.5n个节点的链1。然后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成为新的根。假设h<=log(w)适用于a和b，我们将证明它也适用于联合。我们知道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 s，所以我们总共得到O(m + n log(n))
于 2013-12-07T16:32:40.397 回答