Изменения

!<tex>m \backslash n</tex> !! <tex>0 </tex> !! <tex>1 </tex> !! <tex>2 </tex> !! <tex>3 </tex> !! <tex>4 </tex> !! <tex>5</tex>|- style = "text-align = center"| ! <tex>1 </tex> || <tex>1 </tex> || <tex>2 </tex> || <tex>4 </tex> || <tex>8 </tex> || <tex>16 </tex> || <tex>32</tex>

| ! <tex>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>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>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> a </tex> операций <tex> \mathrm{union} </tex> и <tex> b </tex> операций <tex> \mathrm{get} </tex> (<tex> b > a ) </tex>).

<tex>^*</tex><tex>\mathrm(\log^*n)</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex> (Например: <tex>\mathrm(\log^*_2 16) = 3</tex>)

В процессе выполнения каждой из операций <tex>get</tex> двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Заметим, что на каждом шаге ранг вершины строго возрастает: если <tex>\mathrm{u}</tex> - вершина, встретившаяся на пути поиска, а <tex>\mathrm{v}</tex> - следующая вершина, то есть <tex>\mathrm{v} = \mathrm{P(vu)} </tex>, то <tex> \mathrm{R(v)} \leqslant \mathrm{R(u)}</tex>. Вершина <tex>\mathrm{u}</tex> может неоднократно встречаться в путях поиска, при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут идти разные вершины: если в некоторый момент за <tex>\mathrm{u}</tex> будет следовать уже не <tex>\mathrm{v}</tex>, а корень дерева, то есть вершина большего ранга, чем <tex>\mathrm{v}</tex>.Наблюдая за ростом ранга при переходе от вершины к её родителю, отдельно оценим количество шагов, при которых ранг сильно растет, а количество шагов, когда он растет не сильно. Выберем в качестве границы некоторую функцию <tex>\mathrm{B(k)}</tex>, определенную для неотрицательных целых <tex>\mathrm{k}</tex>. Мы предполагаем, что функция <tex>\mathrm{B}</tex> является монотонно возрастающей и что <tex>\mathrm{B(k)} \leqslant \mathrm{k}</tex> при всех <tex>\mathrm{k}</tex>. При переходе от вершины <tex>\mathrm{u}</tex> к её родителю <tex>\mathrm{v} = \mathrm{P(vu)} </tex> ранг сильно растет сильно растет, если <tex> \mathrm{R(v)} \geqslant \mathrm{B(R(u))} </tex>. Оценим число шагов, при которых ранг не сильно растет, и сгруппируем их по вершинам, из которых этот шаг делается. Для вершины ранга <tex>\mathrm{k}</tex> ранги ее предка могут меняться от <tex>\mathrm{k+1}</tex> до <tex>\mathrm{B(k)}</tex>(после этого ранг растет сильно). Значит, число таких шагов(из данной вершины ранга <tex>\mathrm{k}</tex>) заведомо не больше <tex>\mathrm{B(k)}</tex>, поскольку каждый новый шаг ведёт в вершину большего ранга, чем предыдущий. Поскольку вершин ранга <tex>\mathrm{k}</tex> не более <tex>n/2^{k}</tex>, то общее число шагов, при которых ранг не сильно растет, не превосходит

Прежде чем выбрать функцию <tex>\mathrm{B(k)}</tex>, выясним, как оценить число шагов, при которых ранг сильно растет. Такие шаги мы сгруппируем не по вершинам, а по путям: на каждом пути поиска таких шагов мало, так как ранг не может многократно сильно расти(он меняется всего лишь от <tex>0</tex> и <tex>\log n</tex>). Таким образом, на каждом пути число шагов, при котором ранг сильно растёт, не превосходит числа итераций функции <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы дойти от <tex>0</tex> и <tex>\log n</tex>.Если положить <tex>\mathrm{B(k)} = 2^{\mathrm{k}}</tex>: тогда число итераций будет примерно равно <tex>\mathrm{O(\log^{*}n)}</tex>. Но тогда написанный выше ряд расходится. Возьмем меньшую функцию. Например, положим <tex>\mathrm{B(k)} = 1,9^{\mathrm{k}}</tex>, тогда ряд <tex>\sum_{} \limits \mathrm{B(k)} = 1,9^{\mathrm{k}}/2^{\mathrm{k}} \leqslant \sum_{} \limits \mathrm{B(k)} = (1,9^{\mathrm{k}}+1)/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))} \geqslant 2^{\mathrm{k}}</tex>, и потому есть <tex>\mathrm{O(\log^*n)}</tex>.Теорема доказана.