Изменения

'''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>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> выполняется за константное время.

{{Определение|definition=<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>m\geqslant n</tex>, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex> a ) n</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{get} </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{R(Pget(u))}</tex> возрастает после каждого вызова функции текущее значение <tex>get\mathrm{R(P(u))}</tex>возрастает.Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{union(v, u)}</tex>, и <tex>m\geqslant n</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>. Оставшиеся вершины разделим на:#Быстро растущие вызовы — такие что <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>;#Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</tex>.

3. Быстро растущие вызовы — такие что При каждом вложенном вызове функции <tex>\mathrm{R(Pget(u))} \geqslant </tex> ранг вершины по условию возрастает на <tex>i^{\mathrm{R(u)}}</tex>, где . Ранг вершины может меняться в пределах от <tex>i1</tex> — число из диапазона до <tex dpi="150">e ^{\frac{1}{e}} < i < 2log_2n</tex>; 4. Медленно растущие вызовы — Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(P(u)n)} < i^{\mathrm{R(u)}}</tex>. Для первых двух типов вершин одна операция числа <tex>get(u)</tex> работает за истинное время <tex>\mathrm{O(1)}i</tex>, поэтому их суммарное время работы не превышает необходимых для достижения числа <tex>2\cdot mlog_2n</tex>. Количество итераций для быстро растущих вызовов не превосходит Или что то же самое, количеству логарифмирований по основанию <tex>\log_2 ni</tex>, так как при каждом вызове ранг вершины увеличивается, но он не может быть больше числа <tex>\log_2n</tex>. Таким образом, время на один быстро растущий вызов функции для получения <tex>get(u)1</tex> меньше или равно . Последняя операция описывается функцией <tex dpi="150130">\log^*_{i} \left (\log log_2 n \right )</tex>. Суммарное Тогда время работы <tex>m</tex> быстро растущих вызовов равняется равно <tex>\mathrm{O(m\cdot \log^* n)}</tex>.

В итоге получаем, что суммарное время работы операции <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>.