223
правки
Изменения
Нет описания правки
===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get'' и делает ее двухпроходной. Операция get вызывается для элемента ''x'' (''get(x)''), проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим их напрямую (изменим ссылки) к корню дерева и, таким образом , уменьшим его высоту.
==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''
Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:
{| class="wikitable" border = 1, style="text-align: right;"
|- bgcolor=#FFFFFF
! get || a(m,n)
|-
! union || 1
|-
! m*get + n*union || m*a(m,n) + n
|}
где m - общее количество операций, n - полное количество элементов, a(m, n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой. Таким образом, при этой реализации время работы линейно зависит от количества операций.
==Ссылки==
