并查集路径压缩比rank版本要慢

来源：6-6 路径压缩 (Path Compression)

北半球先生

2019-12-16

如题，java8中测试了10000000的数据量，路径压缩要比rank版本慢，而且如果同时做路径压缩和rank优化更慢

写回答

1回答

liuyubobobo

2019-12-16

我只能说有可能。其实测试路径压缩的效率，关键不是数据量多少，而是合并过程，是否会形成超级长的链条。如果会产生诸如 1 <- 2 <- 3 <- 4 <- 5 ... <- 10000 这样的链，路径压缩一定优于没有路径压缩。

但如果你的测试用例不产生这种长链，那么路径压缩过程本身是额外的操作，自然会有更多的消耗。但是应该不会把性能拖累的太差。

继续加油！：）

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1