Изменения

Сама по себе такая реализация еще не дает выигрыша В худшем случае, дерево может выродиться в скоростилинейный список и get будет работать за линейное время, в сравнении и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализациямиреализацими]], так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get не будет работать за линейное время. Сильный выигрыш в скорости даст использование двух эвристик: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

Эта эвристика несколько модифицирует операцию ''get'' и делает ее двухпроходной. Операция get вызывается для элемента ''x'' (''get(x)''), проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим (изменим ссылки) их напрямую к корню дерева и, таким образом, уменьшим его высоту. При нерукурсивной реализации операция ''get'' становится двухпроходной.

Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:{| class="wikitable" border = 1, style="text-align: right;"|- bgcolor=#FFFFFF! get || a(n)

! union Операция !! Истинное время !! Амортизированное время|- style = "text-align = center"| ''get'' || O(log(n)) || 1O*(α(n))

! | ''union'' || O(1) || O(1)|-| m*''get '' + n*''union '' || O(m*log(n) + n) || O(m*aα(n) + n)

где m - общее количество операций,  n - полное количество элементов, a α(n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.  Таким образом, при этой реализации общее время работы линейно зависит от количества операций.