Изменения

Система непересекающихся множеств. Реализация Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с помощью леса корневых деревьевэтой структурой данных. А именно, обе операции (disjoint set <tex>\mathrm{get}</tex> и <tex>\mathrm{union (DSU}</tex>) или Union-Find)выполняются в среднем за практически константное время.

Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах вершинах дерева. У каждого множества есть его представитель {{- --}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме элемента множествакорня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').

Сама по себе такая реализация еще не дает выигрыша Без использования дополнительных "улучшений", такое дерево может выродиться в скоростилинейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, в сравнении и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализациями]], так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get не будет работать за линейное время. Сильный выигрыш Выигрыш в скорости даст использование двух эвристикможно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней границей оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1<tex>0</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое, к какому дереву подвешивать, но ранг объединенного дерева будет больше следует делать большим на <tex>1</tex>.

Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>'' и делает ее двухпроходной. Операция <tex>\mathrm{get }</tex> вызывается для элемента ''<tex>x'' (''get(x)'')</tex>, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''<tex>x''</tex>. Поэтому подвесим их напрямую мы можем подвесить (изменим изменить ссылки) эти вершины напрямую к корню дерева и, таким образом уменьшим , уменьшить его высоту.При нерекурсивной реализации операция ''<tex>\mathrm{get}</tex>'' становится двухпроходной. ===Псевдокод===Для реализации СНМ будем поддерживать следующие массивы: <tex>p[x]</tex> {{---}} массив "родителей", <tex>r[x]</tex> {{---}} массив рангов.===='''get'''==== '''function''' '''get'''(x: '''int'''): '''int''' '''if''' p[x] != x p[x] = get(p[x]) '''return''' p[x] ===='''union'''==== '''function''' '''union'''(x: '''int''', y: '''int'''): x = get(x) y = get(y) '''if''' x == y '''return''' '''if''' r[x] == r[y] r[x]++ '''if''' r[x] < r[y] p[x] = y '''else''' p[y] = x Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{O(\log n)}</tex> дополнительной памяти. ===='''get'''==== '''function''' '''get'''(x: '''int'''): '''int''' root = x '''while''' p[root] != root root = p[root] i = x '''while''' p[i] != i j = p[i] p[i] = root i = j '''return''' root

Реализация системы непересекающихся множеств :''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:ранговой эвристикой]]'' {| class="wikitable" border = 1, |-!Операция !! Истинное время !! Амортизированное время|- style="text-align: right;= center"| ''<tex>\mathrm{get}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex> |- bgcolor=#FFFFFF! get |''<tex>\mathrm{union}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>| }Где <tex>m</tex> {{---}} общее количество операций, <tex>n</tex> {{---}} полное количество элементов, <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций <tex>\mathrm{get}</tex> и <tex>n</tex> элементов). Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n</tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим. Будем доказывать данное свойство по индукции. Для <tex>k = 0</tex>, очевидно, в множестве содержится <tex>1</tex> вершина. Пусть для множеств ранга <tex>k - 1</tex> свойство выполняется. Как следует из ранговой эвристики, множество ранга <tex>k</tex> может получиться только при подвешивании множества ранга <tex>k - 1</tex> к множеству ранга <tex>k - 1</tex>. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать. ===Функция Аккермана=== Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>: <tex>\mathrm{A(m, n)} = \begin{cases} 2^n, & m = 1 \\ 2, & m > 1, n = 0 \\ a\mathrm{A(m - 1, A(m,n- 1) )}, & m > 1, n > 0\end{cases} </tex> Таблица значений функции Аккермана: {| class="wikitable" border = 1|-!<tex>\mathbf{m \backslash n}</tex> !! <tex>\mathbf{0}</tex> !! <tex>\mathbf{1}</tex> !! <tex>\mathbf{2}</tex> !! <tex>\mathbf{3}</tex> !! <tex>\mathbf{4}</tex> !! <tex>\mathbf{5}</tex>|-style = "text-align = center"! <tex>\mathbf{1}</tex> | <tex>1</tex> || <tex>2</tex> || <tex>4</tex> || <tex>8</tex> || <tex>16</tex> || <tex>32</tex>|-! <tex>\mathbf{2}</tex> | <tex>2</tex> || <tex>4</tex> || <tex>16</tex> || <tex>65536</tex> || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>

! union <tex>\mathbf{3}</tex> |<tex>2</tex> | 1| <tex>16</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>

! m*get + n*union <tex>\mathbf{4}</tex> |<tex>2</tex> | m*a(m,n) + n| <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>

Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex>, равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\dfrac{m}{n} \right ] \right )} \geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция <tex>\mathrm{get}</tex> выполняется за константное время. ===Анализ реализации с ранговой эвристикой=== Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)} </tex>.{{Определение|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm{\log^*n}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>.}}'''Пример''': <tex>\mathrm{\log^*_2 16} = 3</tex> Рассмотрим <tex> n </tex> операций <tex> \mathrm{union} </tex> и <tex> m </tex> операций <tex> \mathrm{get} </tex>. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\mathrm{get}</tex>.Не теряя общности, будем считать, что <tex> \mathrm{union} </tex> принимает в качестве аргументов представителей,то есть <tex> \mathrm{union(v_1,v_2)} </tex> заменяем на <tex> \mathrm{union(get(v_1),get(v_2))} </tex>. Оценим стоимость операции <tex> \mathrm{get(v)} </tex>. Обозначим <tex> \mathrm{R(v)} </tex> — ранг вершины, <tex>\mathrm{P(v)}</tex> — представитель множества, содержащего <tex>\mathrm{v}</tex>,<tex> \mathrm{L(v)} </tex> — отец вершины,<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>. {{Утверждение|statement=<tex> \mathrm{R(P(v))} \geqslant \mathrm{R(v)} </tex>|proof=Если <tex>\mathrm{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} =\mathrm{R(v)} </tex>. Иначе, из принципа работы функции <tex> \mathrm{union} </tex> следует:#<tex> \mathrm{R(L(v))}>\mathrm{R(v)} </tex>.#Между <tex> \mathrm{v} </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> \mathrm{v} \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.}} {{Утверждение|statement=Ссылки<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}</tex>|proof=Докажем по индукции:  Для <tex>0</tex> равенство очевидно.Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:<tex>\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i </tex>.}} Из последнего утверждения следует: {{Утверждение|statement=<tex> \mathrm{R(v)} \leqslant \log_2n </tex>}}{{Утверждение|statement=Количество вершин ранга <tex> i \leqslant \dfrac{n} {2^i} </tex>.|proof=Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.}} {{Теорема|statement=Амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)} </tex>|proof= Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(L(u))}</tex> возрастает.Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{union(v, u)}</tex>, и <tex>m\geqslant n</tex>.Разделим все вершины на <tex>4</tex> типа: :1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>.:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\mathrm{get(u)}</tex> будет не больше чем <tex>m</tex>.Оставшиеся вершины разделим на::3. Быстро растущие вызовы — такие что <tex>\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}</tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\frac{1}{e}} < i < 2</tex> <tex dpi="150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex>.:4. Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</tex>. Для первых двух типов вершин одна операция <tex>\mathrm{get(u)}</tex> работает за истинное время <tex>\mathrm{O(1)}</tex>, поэтому их суммарное время работы не превышает <tex>2\cdot m</tex>. При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг по условию возрастает до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>. Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n \right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{O(m\cdot \log^* n)}</tex>. Поскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, то суммарное время работы медленно растущих вызовов равно<center><tex dpi="150">\sum_u \limits i^{\mathrm{R(u)}}=\sum_{k=0}^{\log n} \limits \sum_{\mathrm{{R(u)}=k}} \limits i^k \leqslant \sum_{k=0}^{\log n} \limits i^k \cdot \frac{n}{2^k} \leqslant n \cdot \sum_{k=0}^{\log n} \limits \dfrac{i^k}{2^k} = \mathrm{O(n)}</tex></center>В итоге получаем, что суммарное время работы операции <tex>\mathrm{get(u)}</tex> равняется <tex>T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}</tex>.С учетом того факта что <tex>m\geqslant n</tex>, амортизированное время работы равно <tex>\mathrm{O(\log^* n)}</tex>.}} == См. также ==* [[СНМ (списки с весовой эвристикой)]]* [[СНМ (наивные реализации)]] ==Источники информации==* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{- --}} описание этой реализации на habrahabr.ru]* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{- --}} Википедия]* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4