Какова сложность метода сжатия пути для алгоритма несвязного множества?

Question

Я изучал алгоритм дизъюнкт с объединением по рангу и сжатию пути .

Мне ясно, если используется Union by rank, то сложность find() operation равна O(log(n)).

Но мне интересно, что такое complexity of the path compression technique для алгоритма несвязного множества, если я использую объединение по рангу или не использую объединение по рангу?

Answer 1

Если вы связываете наборы произвольно, а не используете объединение по рангу или объединение по размеру, то только сжатие пути приведет к O (m log n) времени для любой последовательности n союзов и m находок (при m> n).Это делает амортизированную стоимость операции поиска O (log n)

Доказательство трудное, поэтому вот отличное подтверждение: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf