Size 优化 Rank优化对比疑问

Question

UnionFind3 :4.2729478 s
UnionFind4 :4.341375 s

UnionFind3 :4.2402221 s
UnionFind4 :4.2683184 s

UnionFind3 :4.185095 s
UnionFind4 :4.3035511 s

上面三次结果都是在千万的情况下，每次都是size优化优于rank优化

UnionFind3 :0.2544043 s
UnionFind4 :0.2153508 s

UnionFind3 :0.2503376 s
UnionFind4 :0.2095983 s

上面两次结果都是百万的情况下，rank优于size，这是为什么呢？

Answer 1

liuyubobobo 2020-01-20 11:28:29

rank 的优化只是“理论”上比 size 的优化更优，因为“理论”上可以让整个并查集的高度更低。但对于实际情况，有可能因为测试用例本身不会形成那么高的树，从而使得优化本身更费时间（因为需要更多多余的判断和操作）。

这就好比，归并排序理论上比插入排序更快，但是，如果数组本身有序，其实插入排序更快；如果数据量比较小，也很有可能插入排序更快。

所有的优化都不能保证在所有的情况下都更优。关键是：

1）对于极端情况，优化的效果更好；

2）对于平均情况，优化的效果不差。

继续加油！：）