14
правок
Изменения
Нет описания правки
===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим (изменим ссылки) их напрямую к корню дерева и, таким образом, уменьшим его высоту. При нерекурсивной реализации операция ''get'' становится двухпроходной.
===Псевдокод===
Для реализации СНМ будем поддерживать следующие массивы:
<tex>p[x]</tex> {{---}} массив "родителей".
<tex>r[x]</tex> {{---}} массив рангов.
====get====
get(x)
if p[x] != x
p[x] = get(p[x])
return p[x]
====union====
union(x, y)
x = get(x)
y = get(y)
if r[x] == r[y]
r[x]++
if r[x] < r[y]
p[x] = y
else
p[y] = x
==Асимптотика==
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''get'' || <tex>O(\log n)</tex> || <tex>O(\alpha(m, n))</tex>
|-
| ''union'' || <tex>O(1)</tex> || <tex>O(1)</tex>
* n {{---}} полное количество элементов
* <tex>\alpha(m, n)</tex> {{---}} функция, обратная к функции Аккермана . ===Функция Аккермана=== Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>: <tex>A(m, n) = \begin{{-cases} 2^n, & m = 1 \\ 2, & m > 1, n = 0 \\ A(m -1, A(m, n -1)), & m > 1, n > 0\end{cases}} очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.</tex>
==Ссылки==
