Rank與路徑壓縮，兩者優化的 選擇疑問與看法
来源：6-6 路径压缩 (Path Compression)
阿寶1118
2021-08-06
老師您好，關於使用QuickUnion來實作QuickFind的最佳選擇
我個人理解是 如果掌握了路徑壓縮的技巧 是否就可以選擇不使用Rank優化了呢?
因為路徑壓縮與Rank優化 都是為了解決 『樹高』 所帶來的性能影響。
使用Rank來優化樹的高度，目的是為了 盡可能地降低樹高 使得find與union的操作 效能更好
而路徑壓縮 本質上就是把一顆很高的樹 透過跳躍(一次看n個)的方式 來查找(find)根節點
我想提出的問題是
如果我今天要設計一個UnionFind使得此UnionFind能夠適應『大多數』的情況，且性能表現不會落差太大。
以老師您在此章的做法 就是 使用QuickUnion的實作方式，配合Path Compression的優化就好，就不使用Rank優化了。
因為我看了許多同學的提問 也看了您的回答，想請問老師在這篇問題的回答 是否就是我上述的意思呢?
https://coding.imooc.com/learn/questiondetail/RAKpB2XJdJWPbv0E.html
因為Path Compression本質上就是在一邊『跳躍查找』 同時做 『樹的整理』
也就是說 其實Path Compression本質上 就已經包含Rank優化 在做的事情了(避免樹的高度太高)
1回答
-
“rank + 路径压缩”和“只有路径压缩”，在性能上是否完全一致？如果前者比后者更优，到底怎样表现出来?或者具体到底在什么情况下可以非常好的展现出这个性能差距?我也不能举出很好的例子。
因为路径压缩以后，并查集的时间复杂度是 ackerman 的反函数，这个函数近乎就是 O(1) 的，只有在极其海量的数据下才能看到差别。
整体，从实践的角度，你的结论是正确的。一个只有路径压缩的并查集，已经足够应付我见过的所有情况了。甚至对于一般的数据，如果有 rank 的优化，由于多了对 rank 的 if 判断，可能反而一定程度拖慢性能。但是，从理论上，加上 rank 优化是更优的（毕竟在时间复杂度理论上，一个 if 判断的开销是不计的，但实际不是如此。）但不要让我证明这个理论，这超出我的能力范围了：）
继续加油！：）
012021-08-07
相似问题