14
правок
Изменения
Нет описания правки
==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{- --}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''get'' || <tex>O(\log(n)) </tex> || <tex>O*(α\alpha(n)) </tex>
|-
| ''union'' || <tex>O(1) </tex> || <tex>O(1)|-| m*''get'' + n*''union'' || O(m*log(n) + n) || O(m*α(n) + n)</tex>
|}
* m {{- --}} общее количество операций
* n {{- --}} полное количество элементов
Таким образом, общее время работы линейно зависит от количества операций.
==Ссылки==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{- --}} описание этой реализации на habrahabr.ru]* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{--- }} Википедия]
== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)
