<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>.
{{Утверждение
|statement=
<tex> \mathrm{R(P(v))} > \mathrm{R(v)} </tex>
}}
{{Утверждение
|statement=
<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}</tex>
|proof=
В процессе выполнения каждой из операций Рассмотрим все вызовы функции <tex>get(u)</tex> . В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. ЗаметимЕсли вершина <tex>u</tex> не корень и не сын корня, что на каждом шаге ранг вершины строго возрастает: если то <tex>\mathrm{R(P(u))}</tex> - вершина, встретившаяся на пути поиска, а возрастает после каждого вызова функции <tex>get(u)</tex>.Пусть <tex>\mathrm{v}m</tex> - следующая вершина, то есть — количество вызовов операции <tex>\mathrm{v} = \mathrm{Pget(u)} </tex>, то <tex> \mathrm{Rn</tex> — количество вызовов операции <tex>union(v)} \leqslant \mathrm{R(, u)}</tex>. Вершина , и <tex>m\mathrm{u}geqslant n</tex> может неоднократно встречаться в путях поиска, при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут идти разные Разделим все вершинына <tex>4</tex> типа: если в некоторый момент за 1. <tex>\mathrm{u}</tex> будет следовать уже не — корень. Таких вызовов <tex>\mathrm{v}get(u)</tex>, а корень дерева, то есть вершина большего ранга, чем будет ровно <tex>\mathrm{v}m</tex>.; Наблюдая за ростом ранга при переходе от вершины к её родителю, отдельно оценим количество шагов, при которых ранг сильно растет, а количество шагов, когда он растет не сильно2. Выберем в качестве границы некоторую функцию <tex>\mathrm{B(k)}u</tex>, определенную для неотрицательных целых — сын корня. Таких вызовов <tex>\mathrm{k}get(u)</tex>. Мы предполагаем, что функция будет не больше чем <tex>\mathrm{B}m</tex> является монотонно возрастающей и ; Оставшиеся вершины разделим на: 3. Быстро растущие вызовы — такие что <tex>\mathrm{BR(P(ku))} \geqslant i^{\mathrm{kR(u)}}</tex> при всех , где <tex>\mathrm{k}i</tex>. При переходе от вершины — число из диапазона <texdpi="150">e ^{\mathrmfrac{1}{ue}}< i < 2</tex> к её родителю ; 4. Медленно растущие вызовы — <tex>\mathrm{vR(P(u))} = < i^{\mathrm{PR(u)}} </tex> ранг сильно растет сильно растет, если . Для первых двух типов вершин одна операция <tex> \mathrm{Rget(vu)} \geqslant </tex> работает за истинное время <tex>\mathrm{BO(R(u)1)} </tex>. Оценим число шагов, при которых ранг поэтому их суммарное время работы не сильно растет, и сгруппируем их по вершинам, из которых этот шаг делается. Для вершины ранга превышает <tex>2\mathrm{k}cdot m</tex> ранги ее предка могут меняться от . Количество итераций для быстро растущих вызовов не превосходит <tex>\mathrm{k+1}log_2 n</tex> до , так как при каждом вызове ранг вершины увеличивается, но он не может быть больше <tex>\mathrm{B(k)}log_2n</tex> (после этого ранг растет сильно). ЗначитТаким образом, число таких шаговвремя на один быстро растущий вызов функции <tex>get(из данной вершины ранга u)</tex> меньше или равно <tex dpi="150">\mathrmlog^*_{ki}\left (\log n \right )</tex>) заведомо не больше . Суммарное время быстро растущих вызовов равняется <tex>\mathrm{BO(km\cdot \log^* n)}</tex>, поскольку каждый новый шаг ведёт в вершину большего ранга, чем предыдущий. Поскольку количество вершин ранга с рангом <tex>\mathrm{k}</tex> не более превышает число <tex>\dfrac{n/}{2^{k}</tex>, то общее число шагов, при которых ранг не сильно растет, не превосходитсуммарное время работы медленно растущих вызовов равно
<center>
<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>
</center>
Если выбрать функцию <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>.
}}
