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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
Строка 2: Строка 2:
  
 
==Реализация==
 
==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель - один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
+
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
  
 
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').
 
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').
Строка 23: Строка 23:
 
!Операция !! Истинное время !! Амортизированное время
 
!Операция !! Истинное время !! Амортизированное время
 
|- style = "text-align = center"
 
|- style = "text-align = center"
| ''get''                  || O(log(n))       ||  O*(α(n))  
+
| ''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*''get'' + n*''union''  || O(m*log(n) + n) ||  O(m*α(n) + n)
 
 
|}
 
|}
m - общее количество операций
+
* m {{---}} общее количество операций
  
n - полное количество элементов
+
* n {{---}} полное количество элементов
  
α(n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.
+
* <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 [math]O(\log n)[/math] [math]O(\alpha(n))[/math]
union [math]O(1)[/math] [math]O(1)[/math]
  • m — общее количество операций
  • n — полное количество элементов
  • [math]\alpha(n)[/math] — функция, обратная к функции Аккермана — очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.

Таким образом, общее время работы линейно зависит от количества операций.

Ссылки

Литература

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