为什么并查集章节的QuickUnion比QuickFind还要慢呢(章节6-3)

Question

这是使用jdk8的测试结果

quick find

UF1, 50000 union ops, 1166ms

UF1, 50000 is connected ops, 4ms

quick union

UF2, 50000 union ops, 291ms

UF2, 50000 is connected ops, 1418ms

Answer 1

liuyubobobo 2018-01-24 18:28:07

整体来说，原因是因为：在我们这一小节实现的并查集，由于没有顾及并查集的高度问题，所以在n很大的时候，我们的并查集这棵树是高概率高度不平衡，甚至和链表区别不大。此时，并查集的union操作和find操作都是O(h)这个数量级，如果h和n的差别没有那么大的话，并查集整体就体现不出优势；而Quick Find判断isConnected恒定是O(1)的时间复杂度，有很大的优势：）

我们在下一小节开始，马上就会解决这个问题，简单的加上几行代码，你就会看到QuickUnion的思路快的飞起来：）

• 提问者 伟少_will #1

  非常感谢！

Answer 2

提问者 伟少_will 2018-01-24 18:20:39

我把quick union的测试用例修改了一下, 先进行isconnected操作, 再进行union操作, 效率就有了很大的提高, 我感觉主要是union操作把树的高度提高了不少, 从而导致了is connected的效率下降

quick find

UF1, 50000 union ops, 1221ms

UF1, 50000 is connected ops, 4ms

quick union

UF2, 50000 is connected ops, 5ms

UF2, 50000 union ops, 275ms

• liuyubobobo #1

  感谢补充：）如果先运行isConnected，此时我们没有进行任何Union操作，所以我们的并查集就是一群高度仅为1的树。这时候，isConnected的时间复杂度也退化到O(1)了：）