在Kruskal的算法中使用union-find是否会影响最坏情况的运行时？

Question

所以我现在正在教自己一些图形算法,现在在Kruskal上,并且理解建议使用union-find,因此检查添加边创建一个循环是否只需要O(Log V)时间.出于实际目的,我明白你为什么要这么做,但是严格地看一下Big O符号,这样做实际上是否会影响最坏情况的复杂性？

我的理由:如果不是联合查找,我们做了一个DFS来检查周期,那个运行时间是O(E + V),你必须为O的运行时间执行那个V次(V ^ 2 + VE ).它不仅仅是union find,也就是O(V*LogV),但Kruskal的大部分复杂性来自于删除优先级队列的最小元素E次,即O(E*logE),大O回答.我没有真正看到空间优势,因为union-find需要O(V)空间,因此使用DFS查找循环所需的数据结构也是如此.

所以对一个简单的问题可能是一个过长的解释:在Kruskal的算法中使用union-find是否会影响最坏情况的运行时？

Answer 1

并且了解建议使用union-find,以便检查添加边创建循环是否只需要O(Log V)时间

这不对.使用union find是O(alpha(n) * m),alpha(n)Ackermann函数的倒数在哪里,并且,对于所有意图和目的,可以认为是常数.比对数快得多:

由于alpha(n)是此函数的反函数,alpha(n)因此对于所有远程实用值,小于5 n.因此,每次操作的摊销运行时间实际上是一个很小的常数.

但Kruskal的大部分复杂性来自于删除E次优先级队列的最小元素

这也是错误的.Kruskal的算法不涉及使用任何优先级队列.它涉及在开始时按成本对边缘进行分类.虽然复杂性仍然是你提到的这一步骤.但是,实际排序可能比优先级队列更快(使用优先级队列最多等同于堆排序,这不是最快的排序算法).

底线,如果m是边n数和节点数:

1. 对边缘进行排序:O(m log m).

2. 对于每个边缘,调用union-find:O(m * alpha(n))或基本上只是O(m).

3. 总复杂性:O(m log m + m * alpha(n)).

4. 如果你不使用union-find O(m log m + m * (n + m)),那么如果我们使用你的O(n + m)循环查找算法,那么总复杂性将是如此.虽然O(n + m)这个步骤可能是轻描淡写,因为你还必须以某种方式更新你的结构(插入边缘).天真的不相交集算法实际上O(n log n)是更糟糕的.

注意:在这种情况下,你可以写log n而不是log m你喜欢,因为m = O(n^2)和log(n^2) = 2log n.

总之:是的,union-find 有很多帮助.

即使您使用O(log n)union-find 的变体,这会导致O(m log m + m log n)您可以吸收的完全复杂性,但O(m log m)在实践中,如果可以的话,您宁愿保持第二部分更快.由于union-find很容易实现,所以没有理由不这样做.