1回答

liuyubobobo

2020-01-20

已采纳

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

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

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

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

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

继续加油！：）

6

0