Какова сложность метода сжатия пути для алгоритма несвязного множества? - PullRequest
0 голосов
/ 21 мая 2019

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

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

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

1 Ответ

2 голосов
/ 21 мая 2019

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

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

...