Изменения

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <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>\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} ( b </tex>. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <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>.

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

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

В процессе выполнения каждой из операций Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex> . В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. ЗаметимЕсли вершина <tex>u</tex> не корень и не сын корня, что на каждом шаге ранг вершины строго возрастает: если то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> - вершина, встретившаяся на пути поиска, а текущее значение <tex>\mathrm{vR(L(u))}</tex> - следующая вершина, то есть возрастает.Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{v} = \mathrm{Pget(u)} </tex>, то <tex>n</tex> — количество вызовов операции <tex> \mathrm{Runion(v, u)} </tex>, и <tex>m\leqslant geqslant n</tex>.Разделим все вершины на <tex>4</tex> типа: :1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{Rget(u)}</tex>. Вершина будет ровно <tex>\mathrm{u}m</tex> может неоднократно встречаться в путях поиска, при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут идти разные вершины: если в некоторый момент за 2. <tex>\mathrm{u}</tex> будет следовать уже не — сын корня. Таких вызовов <tex>\mathrm{vget(u)}</tex>, а корень дерева, то есть вершина большего ранга, будет не больше чем <tex>\mathrm{v}m</tex>.Наблюдая за ростом ранга при переходе от Оставшиеся вершины к её родителю, отдельно оценим количество шагов, при которых ранг сильно растет, а количество шагов, когда он растет не сильноразделим на::3. Выберем в качестве границы некоторую функцию Быстро растущие вызовы — такие что <tex>\mathrm{BR(P(u))} \geqslant i^{\mathrm{R(ku)}}</tex>, определенную для неотрицательных целых где <tex>i</tex> — число из диапазона <texdpi="150">e ^{\mathrmfrac{1}{ke}}< i < 2</tex>. Мы предполагаем, что функция <texdpi="150">(e ^{\mathrmfrac{1}{Be}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex> является монотонно возрастающей и что .:4. Медленно растущие вызовы — <tex>\mathrm{BR(P(ku))} \geqslant < i^{\mathrm{kR(u)}}</tex> при всех . Для первых двух типов вершин одна операция <tex>\mathrm{kget(u)}</tex>. При переходе от вершины работает за истинное время <tex>\mathrm{uO(1)}</tex> к её родителю , поэтому их суммарное время работы не превышает <tex>2\mathrm{v} = cdot m</tex>. При каждом вложенном вызове функции <tex>\mathrm{Pget(u)} </tex> для вершин третьего типа ранг сильно растет сильно растет, если по условию возрастает до <tex> i^{\mathrm{R(vu)} }</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\geqslant log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{B(R(u)n)} </tex> числа <tex>i</tex>,необходимых для достижения числа <tex>\log_2n</tex>. Оценим число шагов, при которых ранг не сильно растетИли что то же самое, и сгруппируем их количеству логарифмирований по вершинам, из которых этот шаг делается. Для вершины ранга основанию <tex>i</tex> числа <tex>\mathrm{k}log_2n</tex> ранги ее предка могут меняться от для получения <tex>\mathrm{k+1}</tex> до и еще одному логарифмированию для получения <tex>0</tex>. Количество логарифмирований описывается функцией <texdpi="130">\mathrmlog^*_{Bi} \left (k\log_2 n \right )}</tex> (после этого ранг растет сильно). Значит, число таких шагов(из данной вершины ранга С учетом последнего логарифмирования формула примет вид <texdpi="130">\mathrmlog^*_{ki}n</tex>.Тогда время работы <tex>m</tex>) заведомо не больше быстро растущих вызовов равно <tex>\mathrm{BO(km\cdot \log^* n)}</tex>, поскольку каждый новый шаг ведёт в вершину большего ранга, чем предыдущий.  Поскольку количество вершин ранга с рангом <tex>\mathrm{k}</tex> не более превышает число <tex>\dfrac{n/}{2^{k}</tex>, то общее число шагов, при которых ранг не сильно растет, не превосходитсуммарное время работы медленно растущих вызовов равно

<texdpi="150">\sum_u \limits i^{\sum_mathrm{R(u)}}=\mathrmsum_{k=0}^{\log n} \limits {\dfrac sum_{n \mathrm{B{R(u)}=k}} \limits i^k)\leqslant \sum_{k=0}^{\log n}\limits i^k \cdot \frac{n} {2^{k} \leqslant n \cdot \mathrmsum_{k=0}^{\log n}\limits \dfrac{i^k}{2^k}= \mathrm{O(n)}</tex>

Если выбрать функцию <tex>\mathrm{B}</tex> такВ итоге получаем, чтобы ряд что суммарное время работы операции <tex>{\sum_{} \limits n \mathrm{Bget(ku)} / 2^{\mathrm{k}}}</tex> сходился, то общее число шагов такого рода есть равняется <tex>T = \mathrm{O(nm)}</tex>.Прежде чем выбрать функцию <tex>+ \mathrm{BO(k)}</tex>, выясним, как оценить число шагов, при которых ранг сильно растет. Такие шаги мы сгруппируем не по вершинам, а по путям: на каждом пути поиска таких шагов мало, так как ранг не может многократно сильно расти (он меняется всего лишь от <tex>0</tex> и <tex>m\cdot \log ^* n</tex>). Таким образом, на каждом пути число шагов, при котором ранг сильно растёт, не превосходит числа итераций функции <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы дойти от <tex>0</tex> и <tex>\log n</tex>.Если положить <tex>+\mathrm{BO(kn)} = 2^{\mathrm{k}}</tex>: тогда число итераций будет примерно равно <tex>\mathrm{O(m\cdot \log^{*}n)}</tex>. Но тогда написанный выше ряд расходится. Возьмем меньшую функцию. Например, положим <tex>\mathrm{B(k)} = \lceil 1,9^{\mathrm{k}} \rceil </tex>, тогда ряд <tex>\sum_{} \limits \mathrm{B(k)} = \lceil 1,9^{\mathrm{k}} \rceil /2^{\mathrm{k}} \leqslant \sum_{} \limits \mathrm{B(k)} = (1,9^{\mathrm{k}}+1n)/2^{\mathrm{k}}</tex> сходится. С другой стороны, число итераций функции учетом того факта что <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы от <tex>0</tex> дойти до какого-то числа, возрастет (по сравнению с функцией <tex>\mathrm{k}</tex>, стремящейся к <tex>2^{\mathrm{k}}</tex>) не более чем вдвое, поскольку <tex>\mathrm{B(B(k))} m\geqslant 2^{\mathrm{k}}n</tex>, и потому есть амортизированное время работы равно <tex>\mathrm{O(\log^*n)}</tex>.