Изменения

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

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

'''function''' '''get'''(x: '''int'''): '''int''' '''if''' p[x] != x p[x] = get(p[x]) '''return''' p[x]

'''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

Где <tex>m</tex> {{---}} общее количество операций, <tex>n</tex> {{---}} полное количество элементов, <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций <tex>\mathrm{get }</tex> и <tex>n</tex> элементов).

!<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>

| ! <tex>\mathbf{3 }</tex> || <tex>2 </tex> || <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>

| ! <tex>\mathbf{4 }</tex> || <tex>2 </tex> || <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> a n </tex> операций <tex> \mathrm{union} </tex> и <tex> b 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> b дважды вызывается операция <tex> a \mathrm{get}</tex>).Не теряя общности, будем считать, что <tex> \mathrm{union } </tex> принимает в качестве аргументов представителей,

{{Утверждение

<tex> \mathrm{R(P(v))} > \geqslant \mathrm{R(v)} </tex>

Из Если <tex>\mathrm{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} = \mathrm{R(v)} </tex>. Иначе, из принципа работы функции <tex> \mathrm{getunion} </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>.

{{Утверждение

<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i }</tex>

#{{Утверждение|statement=<tex> \mathrm{R(v)} \leqslant \log_2a log_2n </tex>.#}}{{Утверждение|statement=Количество вершин ранга <tex> i \leqslant \dfrac{n} {a \over 2^i} </tex>.|proof=Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.}}

Амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}an)} </tex>

#Ведут Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень или в сына и не сын корня.#, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex> \mathrm{R(PL(vu))} </tex> возрастает.Пусть <tex>m</tex> — количество вызовов операции <tex>\geqslant x^mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{Runion(v, u)}}</tex>, и <tex>m\geqslant n</tex>.#Все остальные.Разделим все вершины на <tex>4</tex> типа:

Обозначим эти классы :1. <tex> T_1u</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>, T_2, T_3 где <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>.

<center>При каждом вложенном вызове функции <tex>S = {\sum_{\mathrm{get}} \limits} ({\sum_{v:v \in \mathrm{getu)},v \in T_1} \limits 1}+</tex> для вершин третьего типа ранг по условию возрастает до <tex>i^{\sum_{v:v \in \mathrm{get},v \in T_2R(u)} \limits 1} + {</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\sum_{v: \in log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{getR(n)},v \in T_3} \limits 1} ) </ b tex> числа </tex>,i</centertex>,где необходимых для достижения числа <tex> {v \in \mathrm{get} } log_2n</tex> означает, . Или что реброто же самое, начало которого находится в количеству логарифмирований по основанию <tex> v i</tex>, было пройдено во время выполнения текущего числа <tex> \mathrm{get} log_2n</tex> для получения <tex>1</tex>. Ребро и еще одному логарифмированию для получения <tex> v 0</tex> эквивалентно вершине, в которой оно начинается. В силу того, что Количество логарифмирований описывается функцией <texdpi="130">{\sum_log^*_{v:v i} \in left (\mathrm{get},v log_2 n \in T_1} right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\limits 1log^*_{i} = n</tex>.Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{O(1m\cdot \log^* n)} </tex> получаем:.

<texdpi="150">S = \sum_u \limits i^{\mathrm{OR(1u)} + {}=\sum_{k=0}^{\mathrm{get}log n} \limits} ~ {\sum_{v:v \in \mathrm{get{R(u)}=k},v \in T_2} \limits} 1/b+ {i^k \leqslant \sum_{k=0}^{\mathrm{get}log n} \limitsi^k \cdot \frac{n} ~ {2^k} \leqslant n \cdot \sum_{v:v k=0}^{\in log n} \limits \mathrmdfrac{geti^k},v \in T_3{2^k} = \limitsmathrm{O(n)} 1 / b</tex>.

Во время <tex> \mathrm{get} </tex> после прохождения <tex>K</tex> ребер из второго класса <tex> \mathrm{R(v_1)} \geqslant x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>. Из выше сказанного и первого следствия второго утверждения получаем, что:<center><tex> {\sum_{v:v \in \mathrm{get},v \in T_2} \limits} \leqslant \mathrm{\log^*_x(\log_2a)} = \mathrm{O(\log^*a)}</tex>.</center> Для того, чтобы <tex> \mathrm{\log^*_x(\log_2a)} </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.  Рассмотрим сумму<center> <tex>{\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/b < {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a </tex>. </center> Из первого утверждения и в силу использования сжатия путей следует,что <tex> \mathrm{R(P(x))}</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>. Как максимум через <tex> x^{\mathrm{R(k)}} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>. <center><tex>{\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{\mathrm{get}: in ~ this ~ \mathrm{get} ~ v \in T_3} \limits } 1/a \leqslant \sum_v \limits x^{\mathrm{R(v)}} /a</tex>См.</center> Из второго следствия второго утверждения следует:<center> <tex> {\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a \leqslant \sum_{Rankтакже =0}^{\log_2a} \limits {\dfrac {ax^{Rank}} {2^{Rank} a}}</tex>.</center> При <tex> x < 2~</tex>:<center><tex>{\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a\leqslant\sum_{Rank=0}^{\log_2a} \limits {\dfrac {x^{Rank}} {2^{Rank}}}\leqslant\sum_{Rank=0}^\infty \limits {\dfrac {x^{Rank}} {2^{Rank}}}\leqslant{ \dfrac {2} {2-x} } = \mathrm{O* [[СНМ (1списки с весовой эвристикой)}</tex>.</center>  ]]Итак <tex> S = \mathrm{O(1)} + \mathrm{O(\log^*x)} + \mathrm{O[[СНМ (1наивные реализации)} = \mathrm{O(\log^*x)} </tex>.В силу того, что интервал <tex>(1.45; 2)</tex> не пустой, теорема доказана. }}]]

== См. также ==* [[СНМ (списки с весовой эвристикой)Категория: Дискретная математика и алгоритмы]]* [[СНМ (наивные реализации)Категория: Структуры данных]]