СНМ (реализация с помощью леса корневых деревьев) — различия между версиями
м |
|||
| Строка 6: | Строка 6: | ||
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get''). | При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get''). | ||
| − | + | В худшем случае, дерево может выродиться в линейный список и get будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Сильный выигрыш в скорости даст использование двух эвристик: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression). | |
===Объединение по рангу=== | ===Объединение по рангу=== | ||
| Строка 14: | Строка 14: | ||
===Сжатие пути=== | ===Сжатие пути=== | ||
| − | Эта эвристика несколько модифицирует операцию ''get'' | + | Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим (изменим ссылки) их напрямую к корню дерева и, таким образом, уменьшим его высоту. При нерукурсивной реализации операция ''get'' становится двухпроходной. |
==Асимптотика== | ==Асимптотика== | ||
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]'' | :''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]'' | ||
| − | + | {| class="wikitable" border = 1 | |
| − | {| class="wikitable" border = 1 | ||
| − | |||
| − | |||
|- | |- | ||
| − | ! | + | !Операция !! Истинное время !! Амортизированное время |
| + | |- style = "text-align = center" | ||
| + | | ''get'' || O(log(n)) || O*(α(n)) | ||
|- | |- | ||
| − | + | | ''union'' || O(1) || O(1) | |
| + | |- | ||
| + | | m*''get'' + n*''union'' || O(m*log(n) + n) || O(m*α(n) + n) | ||
|} | |} | ||
| − | + | m - общее количество операций | |
| + | |||
| + | n - полное количество элементов | ||
| + | |||
| + | α(n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой. | ||
| + | |||
| + | Таким образом, общее время работы линейно зависит от количества операций. | ||
==Ссылки== | ==Ссылки== | ||
Версия 22:18, 22 марта 2011
Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find)
Содержание
Реализация
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель - один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме элемента множества, хранится ссылка на "родителя".
При объединении двух множеств, корень одного дерева подвешивается к другому (операция union). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция get).
В худшем случае, дерево может выродиться в линейный список и get будет работать за линейное время, и никакого выигрыша по сравнению с наивными реализацими не будет. Сильный выигрыш в скорости даст использование двух эвристик: объединение по рангу (union by rank) и сжатие пути (path compression).
Объединение по рангу
Эта эвристика аналогична весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на 1.
Сжатие пути
Эта эвристика несколько модифицирует операцию get. Операция get вызывается для элемента x, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и x. Поэтому подвесим (изменим ссылки) их напрямую к корню дерева и, таким образом, уменьшим его высоту. При нерукурсивной реализации операция get становится двухпроходной.
Асимптотика
- см. также Анализ реализации с ранговой эвристикой
| Операция | Истинное время | Амортизированное время |
|---|---|---|
| get | O(log(n)) | O*(α(n)) |
| union | O(1) | O(1) |
| m*get + n*union | O(m*log(n) + n) | O(m*α(n) + n) |
m - общее количество операций
n - полное количество элементов
α(n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.
Таким образом, общее время работы линейно зависит от количества операций.
Ссылки
- Система непересекающихся множеств - описание этой реализации на habrahabr.ru
- Функция Аккермана - Википедия
Литература
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)
