СНМ (реализация с помощью леса корневых деревьев) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} ==Реализация== В ''реализации системы непересекающихся множеств с помощью л…»)
(нет различий)

Версия 19:40, 21 марта 2011

Эта статья находится в разработке!

Реализация

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

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

Асимптотика

Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:

get a(m,n)
union 1
m*get + n*union m*a(m,n) + n

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



Ссылки

Литература

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)