所以我正在教自己一些图形算法，现在在Kruskal上，并且理解建议使用union-find，因此检查添加边创建一个循环是否只需要O（Log V）时间 . 出于实际目的，我明白了你为什么要这么做，但是严格地看一下Big O表示法，这样做实际上会影响最坏情况的复杂性吗？
我的理由：如果不是联合查找，我们做了一个DFS来检查循环，那个运行时将是O（E V），你必须为O（V ^ 2 VE）的运行时执行那个V次 . 它不仅仅是union find，它可能是O（V * LogV），但Kruskal的大部分复杂性来自于删除优先级队列的最小元素E次，即O（E * logE），大O回答 . 我没有真正看到空间优势，因为union-find需要O（V）空间，因此使用DFS查找循环所需的数据结构也是如此 .
所以对一个简单的问题可能过长的解释：在Kruskal的算法中使用union-find是否会影响最坏情况的运行时？
1 回答
这不对 . 使用union find是
O(alpha(n) * m)，其中alpha(n)是Ackermann函数的反函数，并且，对于所有意图和目的，可以认为是常数 . 比对数快得多：这也是错误的 . Kruskal's algorithm不涉及使用任何优先级队列 . 它涉及在开始时按成本对边缘进行分类 . 虽然复杂性仍然是你提到的这一步骤 . 但是，在实践中排序可能比优先级队列更快（使用优先级队列最多等同于堆排序，这不是最快的排序算法） .
底线，如果
m是边数和n节点数：对边缘进行排序：
O(m log m).对于每个边，调用
union-find：O(m * alpha(n))，或者基本上只是O(m).总复杂度：
O(m log m + m * alpha(n)).如果您不使用union-find，如果我们使用
O(n + m)循环查找算法，则总复杂度将为O(m log m + m * (n + m)). 虽然这一步的O(n + m)可能是轻描淡写的，因为你还必须以某种方式更新你的结构（插入边缘） . 天真的不相交集算法实际上是O(n log n)，所以更糟 .Note: 在这种情况下，如果您愿意，可以编写
log n而不是log m，因为m = O(n^2)和log(n^2) = 2log n.总结：是的，union-find帮助 a lot .
即使你使用union-find的
O(log n)变体，这会导致O(m log m + m log n)总复杂度，你可以将其同化为O(m log m)，但实际上你真的没有理由不这样做 .