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