223
правки
Изменения
Новая страница: «{{В разработке}} ==Реализация== В ''реализации системы непересекающихся множеств с помощью л…»
{{В разработке}}
==Реализация==
В ''реализации системы непересекающихся множеств с помощью леса корневых деревьев'' каждое множество представляется в виде дерева, в узлах которого находятся элементы самого множества. Каждое множество идентифицируется по его представителю. Каждый узел дерева хранит в себе ссылку на родителя, а корень дерева ссылается сам на себя и является представителем этого множества. При объединении двух множеств, один из корней деревьев подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по дереву вверх до корня (операция ''get'').
Сама по себе такая реализация еще не дает выигрыша в скорости, по сравнению с [[СНМ(наивные_реализации)|наивными реализациями]], так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Выигрыш в скорости даёт использование двух эвристик: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
==Асимптотика==
Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:
{| class="wikitable" border = 1, style="text-align: right; margin-left: auto; margin-right: auto;"
|- bgcolor=#FFFFFF
! get || a(m,n)
|-
! union || 1
|-
! m*get + n*union || m*a(m,n) + n
|}
где m - общее количество операций, n - полное количество элементов, a(m, n) - обратная функция к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.
==Ссылки==
* [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)
==Реализация==
В ''реализации системы непересекающихся множеств с помощью леса корневых деревьев'' каждое множество представляется в виде дерева, в узлах которого находятся элементы самого множества. Каждое множество идентифицируется по его представителю. Каждый узел дерева хранит в себе ссылку на родителя, а корень дерева ссылается сам на себя и является представителем этого множества. При объединении двух множеств, один из корней деревьев подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по дереву вверх до корня (операция ''get'').
Сама по себе такая реализация еще не дает выигрыша в скорости, по сравнению с [[СНМ(наивные_реализации)|наивными реализациями]], так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Выигрыш в скорости даёт использование двух эвристик: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
==Асимптотика==
Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:
{| class="wikitable" border = 1, style="text-align: right; margin-left: auto; margin-right: auto;"
|- bgcolor=#FFFFFF
! get || a(m,n)
|-
! union || 1
|-
! m*get + n*union || m*a(m,n) + n
|}
где m - общее количество операций, n - полное количество элементов, a(m, n) - обратная функция к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.
==Ссылки==
* [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)
