Mui*_*hin 2 algorithm disjoint-sets union-find
我正在研究通过等级和路径压缩并集的不相交算法。
我很清楚如果Union by rank使用那么find() operation复杂性是O(log(n))。
但我想知道complexity of the path compression technique如果我使用按等级并集或不使用按等级并集，不相交集算法是什么？
如果您将集合任意链接在一起，而不是使用按等级并集或按大小并集，则对于任何n个并集和m 个查找（其中 m > n）的序列，单独的路径压缩将实现O(m log n)时间。这使得查找操作的摊余成本为 O(log n)
证明很困难，所以这里有一个很好的验证参考：https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf