\Section{Хорошие оценки на время работы СНМ}{4 Декабря}{Веселов Иван}
	\Subsection{Введение}\\
    В СНМ содержится $n$ элементов. Подразумевается, что СНМ использует обе эвристики: сжатие путей и ранговую.
    За все время работы к СНМ было сделано $m$ запросов типа $get$ и $q$ запросов типа $join$.
    \begin{Def}
      Ранг. Каждому элементу $e$ сопоставляется число $r_{e} \in \mathbb{N} \cup \{0\}$, которое называется
      рангом элемента $e$. Изначально $\forall e: r_{e} = 0$. Если объединяются два множества с представителями
      $a$ и $b$, причем $r_{a} = r_{b} = r$, то ранг представителя объединения, будь то $a$ или $b$, становится
      равным $r + 1$, то есть увеличивается на $1$.
    \end{Def}
    
    \begin{Def}
      Предок. Если элемент $e$ не является представителем множества $A$, в котором он лежит, то, в соответствие со
      структурой СНМ, элемент $e$ ссылается на другой элемент $p_{e}$ множества $A$, который называется предком
      элемента $e$.
    \end{Def}
    
    \begin{Lm}
      Если элемент $e$ не является представителем своего множества, то $r_{p_{e}} > r_{e}$.
      \begin{proof}
        Докажем это утверждение, как инвариант:
        \begin{itemize}
          \item Такой инвариант выполнен в самом начале, когда каждый элемент образует одноэлементное множество.
          \item Когда выполняется операция $join$, инвариант сохраняется, так как либо элемент с меньшим рангом
          стал ссылаться на элемент с большим рангом, либо ранги представителей объединяемых множеств были равны,
          но тогда ранг нового представителя станет больше на $1$ и будет больше, чем ранг представителя второго множества.
          \item Когда выполняется операция $get$, инвариант сохраняется, если он был выполнен до этого, так как
          в таком случае ранг представителя множества больше, чем ранг любого другого элемента этого множества, а
          операции $get$ просто перенаправляет ссылки некоторых элементов на представителя. 
        \end{itemize}
        
        Получаем, что данный инвариант сохраняется на протяжении всей работы с СНМ.
      \end{proof}
    \end{Lm}
    
    \begin{Def}
      Размер множества. Если элемент $e$ является представителем своего множества $A$, то $s_{e} := |A|$.
    \end{Def}
    
    \begin{Lm}
      Если элемент $e$ является представителем своего множества, то $2^{r_{e}} \leq s_{e}$.
      \begin{proof}
        Докажем это утверждение, как инвариант:
        \begin{itemize}
          \item Такой инвариант выполнен в самом начале, когда каждый элемент образует одноэлементное множество:
          $2^{r_{e}} = 2^{0} = 1 = s_{e}$.
          \item Когда выполняется операция $join$ (обозначим за $a$ и $b$ представителей объединяемых множеств),
          возможны два варианта: 
            \begin{itemize}
              \item[1.] Ранги представителей различны, тогда:
              $2^{r_{a}} \leq s_{a}, 2^{r_{b}} \leq s_{b} \Rightarrow \max{\{2^{r_{a}}, 2^{r_{b}}\}} \leq \max{\{s_{a}, s_{b}\}} \leq
              s_{a} + s_{b}$.
              \item[2.] Ранги представителей совпали, тогда:
              $r_{a} = r_{b} = r, 2^{r_{a}} \leq s_{a}, 2^{r_{b}} \leq s_{b} \Rightarrow 2^{r + 1} = 2^{r} \cdot 2 = 
              2^{r} + 2^{r} = 2^{r_{a}} + 2^{r_{b}} \leq s_{a} + s_{b}$.
            \end{itemize}
          \item Когда выполняется операция $get$, ни с размером множества, ни с рангом представителя, ничего не происходит,
          значит инвариант сохраняется.
        \end{itemize}
        
        Получаем, что данный инвариант сохраняется на протяжении всей работы с СНМ.
      \end{proof}
    \end{Lm}
    
  \Subsection{Крутые ребра и логарифм со звездочкой}\\
    \begin{Def}
      Крутое ребро. Если элемент $e$ не является представителем своего множества и $r_{p_{e}} \geq 1.7^{r_{e}}$, то
      ссылка элемента $e$ на $p_{e}$ называется крутым ребром (ребро в графе ссылок).
    \end{Def}
    
    \begin{Lm}
      Крутых ребер на пути по ссылкам от $\forall$ элемента $e \in A$ до представителя множества $A$ не больше чем $2\log^{*}_{2}(n)$.
      \begin{proof}
        Докажем от противного, что крутых ребер не больше чем $\log^{*}_{1.7}(n)$:
        пусть крутых ребер на пути $E > \log^{*}_{1.7}(n)$.\\
        Обозначим за $R$ представителя $A$. Докажем, что
        $r_{R} \geq 1.7^{{\dots}^{1.7^{r_{e}}}}$, где количество $1.7$ равно $E$. Ранг элемента $e$ равен $r_{e}$, ранги следующих
        элементов строго больше (по лемме $1.3$). Если ранг некоторого элемента на пути равен $x$, то $x \geq r_{e}$, а если следующее
        ребро на пути является первым крутым ребром на пути, то для ранга следующего на пути элемента $a$ верно, что
        $r_{a} \geq 1.7^{x} \geq 1.7^{r_{e}}$. Проводя данное рассуждение индукционно, получаем требуемое неравенство:
        $r_{R} \geq 1.7^{{\dots}^{1.7^{r_{e}}}}$.\\
        Из полученного неравенства следует что, если $r_{e} > 0$, то $\log^{*}_{1.7}(r_{R}) \geq E > E - 1$, а если $r_{e} = 0$, то
        $\log^{*}_{1.7}(r_{R}) \geq E - 1$. То есть в любом случае $\log^{*}_{1.7}(r_{R}) \geq E - 1 > \log^{*}_{1.7}(n) - 1$. Так как
        это неравенство в целых числах, то из него следует, что $\log^{*}_{1.7}(r_{R}) \geq \log^{*}_{1.7}(n) \Rightarrow r_{R} \geq n
        \Rightarrow 2^{r_{R}} \geq 2^{n} > n \geq s_{R}$. Полученное неравенство противоречит лемме $1.5$, значит предположение неверно и
        $E \leq \log^{*}_{1.7}(n)$.\\
        Имеет место неравенство $\forall x: 1.7^{1.7^{x}} > 2^{x}$. Если $n = 1.7^{\dots^{1.7^{\alpha}}}$, где $0 < \alpha \leq 1$ и количество
        $1.7$ четное (обозначим его за $T_{1.7} = \log^{*}_{1.7}(n)$), то из неравенства следует, что $n > 2^{\dots^{2^{\alpha}}}$,
        где количество $2$ (обозначим за $T_{2}$) в два раза меньше $T_{1.7}$, то есть равно $\frac{T_{1.7}}{2}$. Если $T_{1.7}$ нечетно, то
        $T_{2} = \frac{T_{1.7} - 1}{2}$. В любом случае $n > 2^{\dots^{2^{\alpha}}}$, где $T_{2} \geq \frac{T_{1.7} - 1}{2}$, но тогда
        $\log^{*}_{2}(n) > T_{2} \geq \frac{T_{1.7} - 1}{2} = \frac{\log^{*}_{1.7}(n) - 1}{2} \Rightarrow 2\log^{*}_{2}(n) > \log^{*}_{1.7}(n) - 1
        \Rightarrow 2\log^{*}_{2}(n) \geq \log^{*}_{1.7}(n)$.\\
        Получаем, что $E \leq \log^{*}_{1.7}(n) \leq 2\log^{*}_{2}(n)$.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Если элемент $e$ не является представителем своего множества, то после любой операции ($get$ или $join$) значение
      величины $r_{p_{e}}$ не уменьшилось.
      \begin{proof}
        Отдельно для каждой операции:
        \begin{itemize}
          \item[1.] $get$. После операции либо предок элемента не изменился, тогда $r_{p_{e}}$ тоже, так как после операции $get$
          ранги элементов не меняются, либо предком элемента стал представитель множества, но у представителя множества ранг не меньше,
          чем у всех элементов множества (по лемме $1.3$), включая бывшего предка $e$.
          \item[2.] $join$. После операции предок элемента не изменился, но мог измениться ранг предка. Ранг одного элемента по
          определению не может уменьшится.
        \end{itemize}
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Если элемент $e$ не является представителем своего множества, то $e$ уже никогда не станет представителем своего множества, а 
      величина $r_{e}$ уже никогда не изменится.
      \begin{proof}
        После операции $get$\ $e$ разве что может ссылаться на представителя своего множества. После операции $join$ один из
        двух представителей перестает быть представителем, а новых не появляется.\\
        Ранг элемента меняется только когда происходит операция $join$, причем изменяется ранг элемента, который был
        представителем своего множества. Та как $e$ уже не станет представителем своего множества, а ранг меняется только
        у представителя, то $r_{e}$ больше не изменится.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Пусть некоторый элемент $e$ после операции $join$ перестал быть представителем своего множества. Тогда согласно
      лемме $2.4$ $e$ никогда не станет представителем своего множества, а величина $r_{e}$ не изменится. После $1.7^{r_{e}}$
      операций $get$, которые проходили по ссылке из $e$, когда $p_{e}$ не являлся представителем своего множества, ссылка
      на $p_{e}$ обязательно станет крутым ребром и останется им навсегда.
      \begin{proof}
        Если операция $get$ проходит по ссылке из $e$ не в представителя множества, то после операции ссылка элемента $e$
        изменится на представителя множества, у которого ранг больше хотя бы на $1$ (лемма $1.3$). Так как величина $r_{p_{e}}$
        не уменьшается (лемма $2.3$), то после $1.7^{r_{e}}$ таких операций $get$\ $r_{p_{e}}$ будет хотя бы $1.7^{r_{e}}$.
        Значит через $1.7^{r_{e}}$ таких операций $get$ будет выполнено неравенство $r_{p_{e}} \geq 1.7^{r_{e}}$, что означает, что
        ссылка на $p_{e}$ является крутым ребром. Так как $r_{p_{e}}$ не уменьшается, а $1.7^{r_{e}}$ не изменяется (лемма $2.4$), то
        неравенство будет только усиливаться, а значит ссылка элемента $e$ навсегда останется крутым ребром.
      \end{proof}
    \end{Lm}
    
    \begin{Thm}
      Суммарное время работы всех операций $get$ пропорционально $m\log^{*}(n) + n + m$.
      \begin{proof}
        Время работы $i$-ой операции $get$ пропорционально $\log^{*}(n) + t_{i} + 1$:
        \begin{itemize}
          \item[1.] $\log^{*}(n)$. По лемме $2.2$ количество крутых ребер на пути операции $get$ не больше чем $2\log^{*}(n)$.
          \item[2.] $t_{i}$ означает количество не крутых ребер на пути $i$-ой операции $get$,
          не учитывая последней ссылки в представителя множества. То есть это как раз такие ссылки, которые используются в лемме
          $2.5$.
          \item[3.] $1$. Некоторое константное количество действий для каждой операции $get$. Сюда включен проход по последней
          ссылке в представителя множества, так как это действие не учитывается в пункте $2$ и не всегда учитывается в пункте $1$.
        \end{itemize}
        
        Значит суммарное время работы всех операций $get$ пропорционально $\sum\limits_{i}{(\log^{*}(n) + t_{i} + 1)} = 
        \sum\limits_{i}{\log^{*}(n)} + \sum\limits_{i}{t_{i}} + \sum\limits_{i}{1} = m\log^{*}(n) + \sum\limits_{i}{t_{i}} + m$.\\
        $\sum\limits_{i}{t_{i}} = \sum\limits_{e}{c_{e}}$, где $c_{e}$ суммарное количество переходов по ссылке элемента $e$ всеми
        операциями $get$, когда ссылка элемента $e$ была не крутым ребром, и $p_{v}$ не являлся представителем своего множества. Но
        по лемме $2.5$ величина $c_{e} \leq 1.7^{r_{e}}$ (для каждого элемента берется его ранг в момент, когда элемент перестал
        быть представителем своего множества, по лемме $2.4$ его ранг уже не изменится), так как после такого количества переходов
        по ссылке из $e$ ссылка гарантировано станет крутым ребром и останется им навсегда. Значит
        $\sum\limits_{e}{c_{e}} \leq \sum\limits_{e}{1.7^{r_{e}}}$. Если за $count(r)$ обозначить количество элементов с рангом $r$, то
        $\sum\limits_{e}{1.7^{r_{e}}} = \sum\limits_{r}{1.7^{r} \cdot count(r)}$.\\
        Докажем, что $count(r) \leq \frac{n}{2^{r}}$. От противного: пусть $count(r) > \frac{n}{2^{r}}$. Рассмотрим в хронологическом порядке
        появление каждого элемента $e$ с рангом $r$. Если появляется элемент с рангом $r$, то значит произошла операция $join$, где элемент $e$,
        переставший быть представителем своего множества, имел ранг $r$. Тогда посчитаем по всем таким событиям суммарный размер множеств,
        представителями которых были эти элементы $e$. Эти множества не пересекаются, так как по лемме $1.3$ $r$ наибольший ранг элемента
        в множестве, а значит одно множество не могло содержать предыдущее, так как в предыдущем уже есть элемент с рангом $r$, а пересекаться множества
        не могут, так как в СНМ множества не разбиваются. Значит суммарный размер таких множеств не превосходит количества всех элементов, то есть $n$.
        С другой стороны по лемме $1.5$ размер каждого такого множества хотя бы $2^{r}$, но тогда суммарный размер этих множеств хотя бы 
        $2^{r} \cdot count(r) > 2^{r} \cdot \frac{n}{2^{r}} = n$. Полученное противоречие означает, что предположение неверно, и
        $count(r) \leq \frac{n}{2^{r}}$.\\
        Используя результат предыдущих рассуждений получаем, что $\sum\limits_{r}{1.7^{r} \cdot count(r)} \leq
        \sum\limits_{r}{1.7^{r} \cdot \frac{n}{2^{r}}} = n \cdot \sum\limits_{r}{(\frac{1.7}{2})^{r}}$. Так как $\frac{1.7}{2} < 1$, то сумма
        геометрической прогрессии $\sum\limits_{r}{(\frac{1.7}{2})^{r}}$ не превосходит некоторой константы $C$, а значит
        $n \cdot \sum\limits_{r}{(\frac{1.7}{2})^{r}} \leq n \cdot C$. Получили, что $\sum\limits_{i}{t_{i}} \leq C \cdot n$, то есть, что
        сумма $t_{i}$ пропорциональна $n$.\\
        Получаем, что суммарное время работы всех операций $get$ пропорционально $m\log^{*}(n) + n + m$.
      \end{proof}
    \end{Thm}
    
  \Subsection{Улучшение оценки, растущая крутизна}\\
    \begin{Def}
      Крутизна.\\
      $f(x, y) = \begin{cases}
        0, \text{если}\ x < 1.7^{y}\\
        1 + f(\log_{1.7}(x), y), \text{иначе}
      \end{cases}$\\
      Крутизной элемента $e$ называется число $h_{e} = f(r_{p_{e}}, r_{e})$. Для представителей множеств $h_{e}$ равно $0$.
      Если говорить не строго, то $h_{e}$ означает максимальное количество
      крутых ребер, что пройдя по этим крутым ребрам ранг увеличится не больше, чем если пройти по ссылке из $e$ в $p_{e}$.
    \end{Def}
    
    \begin{Lm}
      Для данного элемента $e$ величина $h_{e}$ не уменьшается.
      \begin{proof}
        По лемме $2.3$ величина $r_{p_{e}}$ не уменьшается. Так как функция $f$ из определения крутизны монотонна при фиксированном
        втором параметре (он не изменяется по лемме $2.4$), то $h_{e}$ не уменьшается.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Для данного элемента $e$ после операции $get$ величина $h_{e}$ выростет хотя бы на количество крутых ребер на пути из $p_{e}$ до
      представителя множества.
      \begin{proof}
        Воспользуемся обозначениями и вспомогательным утвержденим леммы $2.2$.
        $r_{R} \geq 1.7^{{\dots}^{1.7^{r_{p_{e}}}}}$, где количество $1.7$ равно $E$ --- количеству крутых ребер на пути из $p_{e}$ до $R$.
        Тогда новая крутизна $h_{e} = f(r_{R}, r_{e}) \geq f(1.7^{{\dots}^{1.7^{r_{p_{e}}}}}, r_{e}) = E + f(r_{p_{e}}, r_{e})$, то есть
        увеличилась хотя бы на $E$.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Для любого элемента $e$ величина $h_{e} \leq 2\log^{*}(n)$.
      \begin{proof}
        Доказательство аналогично лемме $2.2$, именно в этом смысле крутизна эквивалентна $h_{e}$ крутым ребрам.
      \end{proof}
    \end{Lm}
    
    \begin{Rem}
      $\sum\limits_{e}{h_{e}} \leq 2n\log^{*}(n)$.
    \end{Rem}
    
    \begin{Rem}
      Для данного элемента $e$ после операции $get$ величина $h_{e}$ выростет хотя бы на суммарную крутизну ребер на пути из $p_{e}$ до
      представителя множества.
      \begin{proof}
        Аналогично лемме $3.3$.
      \end{proof}
    \end{Rem}
    
    \begin{Thm}
      Суммарное время работы всех операций $get$ пропорционально $n\log^{*}(n) + n + m$.
      \begin{proof}
        Время работы $i$-ой операции $get$ пропорционально $u_{i} + t_{i} + 1$:
        \begin{itemize}
          \item[1.] $u_{i}$ означает «количество крутых ребер на пути операции минус $1$» или $0$, если крутых ребер нет.
          Логически из рассмотрения выкидывается последнее крутое ребро на пути операции.
          \item[2.] $t_{i}$ аналогично теореме $2.6$.
          \item[3.] $1$. Аналогично теореме $2.6$, но сюда также включен проход по последнему крутому ребру на пути операции.
        \end{itemize}
        
        Значит суммарное время работы всех операций $get$ пропорционально $\sum\limits_{i}{(u_{i} + t_{i} + 1)} = 
        \sum\limits_{i}{u_{i}} + \sum\limits_{i}{t_{i}} + \sum\limits_{i}{1} = \sum\limits_{i}{u_{i}} + \sum\limits_{i}{t_{i}} + m$.
        Из теоремы $2.6$ сумма $\sum\limits_{i}{t_{i}}$ пропорциональна $n$.\\
        У каждого элемента, ссылка которого учтена в $u_{i}$, крутость после операции $get$ увеличится хотя бы на $1$ (лемма $3.3$).
        То есть после $i$-ой операции $get$ суммарная крутость возрастет хотя бы на $u_{i}$, так как крутости остальных элементов не
        уменьшаются (лемма $3.2$). То есть после всех операций $get$ суммарная крутость будет хотя бы $\sum\limits_{i}{u_{i}}$. Но по
        следствию $3.5$: $\sum\limits_{i}{u_{i}} \leq \sum\limits_{e}{h_{e}} \leq 2n\log^{*}(n)$.\\
        Получили, что суммарное время работы всех операций $get$ пропорционально $n\log^{*}(n) + n + m$.
      \end{proof}
    \end{Thm}
    
  \Subsection{Альтернативная оценка, классы крутизны}\\
    \begin{Def}
      Класс крутизны. Каждый элемент $e$ в зависимости от его крутизны попадает в некоторый класс крутизны, который обозначается $c_{e}$.
      А именно: $c_{e} = [\log(h_{e})]$.
    \end{Def}
    
    \begin{Rem}
      Из определения сразу следует, что классов крутизны не больше, чем $\log(\max\limits_{e}\{h_{e}\})$, что не больше, чем
      $\log(2\log^{*}(n)) = \log(\log^{*}(n)) + 1$ (по лемме $3.4$).
    \end{Rem}
    
    \begin{Lm}
      Для данного элемента $e$ величина $c_{e}$ не уменьшается.
      \begin{proof}
        По лемме $3.2$ величина $h_{e}$ не уменьшается. Так как $\log$ монотонная функция, то $c_{e}$ не уменьшается.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Если во время операции $get$ над крутым ребром элемента $e_{1}$ было крутое ребро элемента $e_{2}$
      (то есть $e_{2}$ было на пути до корня позже, чем $e_{1}$), и $c_{e_{1}} \leq c_{e_{2}}$, то класс крутизны элемента $e_{1}$
      после операции $get$ строго увеличится.
      \begin{proof}
        $]\ c'_{e_{1}}$ и $h'_{e_{1}}$ --- это новый класс крутизны и новая крутизна элемента $e_{1}$ соответственно. Тогда по следствию $3.6$:
        $h'_{e_{1}} \geq h_{e_{1}} + h_{e_{2}} = 2^{\log(e_{1})} + 2^{\log(e_{2})} \geq 2^{[\log(e_{1})]} + 2^{[\log(e_{2})]} = 
        2^{c_{e_{1}}} + 2^{c_{e_{2}}} \geq 2^{c_{e_{1}}} + 2^{c_{e_{1}}} = 2 \cdot 2^{c_{e_{1}}} = 2 \cdot 2^{[\log(h_{e_{1}})]}$.
        Тогда $c'_{e_{1}} = \log(h'_{e_{1}}) \geq \log(2 \cdot 2^{[\log(h_{e_{1}})]}) =
        1 + [\log(h_{e_{1}})] = c_{e_{1}} + 1 \Rightarrow c'_{e_{1}} > c_{e_{1}}$.
      \end{proof}
    \end{Lm}
    
    \begin{Thm}
      Суммарное время работы всех операций $get$ пропорционально $(n + m)\log((\log^{*}(n))$.
      \begin{proof}
        Время работы $i$-ой операции $get$ пропорционально $\log((\log^{*}(n)) + v_{i} + t_{i} + 1$:
        \begin{itemize}
          \item[1.] $\log((\log^{*}(n))$. Крутых ребер на пути, у которых класс крутости не поменялся будет не больше,
          чем $\log(\log^{*}(n)) + 1$. Пусть это не так. Но по следствию $4.2$ среди таких ребер существуют два
          с одинаковым классом крутизны, а по лемме $4.4$ одно из них поменяло свой класс крутизны, получили противоречие.
          \item[2.] $v_{i}$ означает количество крутых ребер на пути, у которых класс крутости поменялся.
          \item[3.] $t_{i}$ аналогично теореме $2.6$.
          \item[4.] $1$. Аналогично теореме $2.6$.
        \end{itemize}
        
        Значит суммарное время работы всех операций $get$ пропорционально $\sum\limits_{i}{(\log((\log^{*}(n)) + v_{i} + t_{i} + 1)} = 
        \sum\limits_{i}{\log((\log^{*}(n))} + \sum\limits_{i}{v_{i}} + \sum\limits_{i}{t_{i}} + \sum\limits_{i}{1} =
        m\log((\log^{*}(n)) + \sum\limits_{i}{v_{i}} + \sum\limits_{i}{t_{i}} + m$.
        Из теоремы $2.6$ сумма $\sum\limits_{i}{t_{i}}$ пропорциональна $n$.\\
        Так как у каждого элемента класс крутизны только увеличивается (лемма $4.3$), а классов крутизны не больше чем $\log((\log^{*}(n)) + 1$
        (следствие $4.2$), то каждый элемент будет изменять свой класс крутизны не больше чем $\log((\log^{*}(n)) + 1$ раз.
        Значит $\sum\limits_{i}{v_{i}} \leq n\log((\log^{*}(n))$.\\
        Получили, что суммарное время работы всех операций $get$ пропорционально $(n + m)\log((\log^{*}(n))$.
      \end{proof}
    \end{Thm}
    
  \Subsection{Функция Аккермана}\\
    \begin{Def}
      Функция Аккермана.\\
      $A_{k}(t): \mathbb{N} \rightarrow \mathbb{N}\\
      A_{k}(t) = \begin{cases}
        t + 1, \text{при}\ k = 0\\
        A_{k - 1}^{(t + 1)}(t), \text{иначе}
      \end{cases}$\\
      
      Где $f^{(t)} = f \circ \dots \circ f$\ $t$ раз, то есть композиция функции $f$ с собой $t$ раз.
    \end{Def}
    
    \begin{Lm}
      $A_{k}(t) > t$, $A_{k}$ монотонно возрастает.
      \begin{proof}
        Доказательство по индукции.\\
        База $k = 0$ --- тривиально.\\
        Переход $k - 1 \rightarrow k$. $A_{k}(t) = A_{k - 1}^{(t + 1)}(t)$. Каждое очередное применение функции $A_{k - 1}$
        дает большее чем аргумент число, значит результат больше, чем $t$, то есть $A_{k}(t) = A_{k - 1}^{(t + 1)}(t) > t$.\\
        Так как $t < A_{k - 1}(t)$, то $A_{k - 1}^{(t + 1)}(t) < A_{k - 1}(A_{k - 1}^{(t + 1)}(t)) = A_{k - 1}^{(t + 2)}(t)$.
        Но а так как $A_{k - 1}$ монотонна, то $A_{k}(t) = A_{k - 1}^{(t + 1)}(t) < A_{k - 1}^{(t + 2)}(t + 1) = A_{k}(t + 1)$.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      $f(t) = A_{t}(1)$ монотонно возрастает.
      \begin{proof}
        $A_{t + 1}(1) = A_{t}(A_{t}(1)) > A_{t}(1)$, так как $A_{t}(1) > 1$, а $A_{t}$ монотонна (лемма $5.2$)
      \end{proof}
    \end{Lm}
    
    Выпишем первые несколько функций явно:
    \begin{itemize}
      \item[1.] $A_{1}(t) = A_{0}^{(t + 1)}(t) = 2t + 1$. Последнее равенство доказывается по индукции.
      \item[2.] $A_{2}(t) = A_{1}^{(t + 1)}(t) = 2^{t + 1}(t + 1) - 1 \geq 2^{t}$. Последнее равенство доказывается по индукции.
    \end{itemize}
    
    \begin{Def}
      Обратная функция Аккермана. $\alpha(t) = \min\{k\ |\ A_{k}(1) \geq t\}$
    \end{Def}
    
    Посчитаем несколько первых значений $\alpha$:
    \begin{itemize}
      \item[0.] $A_{0}(1) = 1 + 1 = 2$.
      \item[1.] $A_{1}(1) = 2 \cdot 1 + 1 = 3$.
      \item[2.] $A_{2}(1) = 2^{2} \cdot 2 - 1 = 7$.
      \item[3.] $A_{3}(1) = A_{2}(A_{2}(1)) = A_{2}(7) = 2^{8} \cdot 8 - 1 = 2047$.
      \item[4.] $A_{4}(1) = A_{3}(A_{3}(1)) = A_{3}(2047) = A_{2}^{(2048)}(2047) =
      A_{2}^{(2047)}(A_{2}(2047)) > A_{2}^{(2047)}(2^{2047}) > \dots > 2^{2^{\dots^{2^{2047}}}}$, где количество $2$ равно $2048$.
      Последняя серия неравенст следует из монотонности $A_{2}$ (лемма $5.2$). Получившаяся оценка снизу на $A_{4}(1)$ невероятно большое число,
      превышающее число атомов в наблюдаемой части Вселенной.
    \end{itemize}
    
    Последнее высказывание означает, что для чисел, которые встречаются на практике $\alpha(t) \leq 4$.
    
  \Subsection{СНМ и Аккерман}\\
    \begin{Def}
      Порядок элемента. Для каждого элемента $e$, который не является представителем своего множества, определим величину
      $level(e) = \max\{k\ |\ r_{p_{e}} \geq A_{k}(r_{e})\}$.
    \end{Def}
    
    \begin{Def}
      Характеристика порядка. Для каждого элемента $e$, который не является представителем своего множества, определим величину
      $iter(e) = \max\{k\ |\ r_{p_{e}} \geq A_{level(e)}^{(k)}(r_{e})\}$.
    \end{Def}
    
    \begin{Lm}
      Для любого элемента $e$, не являющегося представителем своего множества, верно, что $0 \leq level(e) < \alpha(n)$.
      \begin{proof}
        $level(e) \geq 0$, так как $A_{0}(r_{e}) = r_{e} + 1 \leq r_{p_{e}}$ по лемме $1.3$.\\
        Пусть $level(e) \geq \alpha(n)$. $k = level(e)$. По определению $r_{p_{e}} \geq A_{k}(r_{e}) \geq A_{k}(1)$, так как
        $A_{k}$ монотонна (лемма $5.2$).\\
        Но ранг любого элемента не превосходит $n - 1$, так как ранг одного элемента
        увеличивается не больше чем на $1$ за одну операцию $join$, но всего операций $join$, которые действительно соединяют
        два множества, может быть не больше чем $n - 1$, так как за одну операцию $join$ количество множеств уменьшается на $1$.\\
        Получаем, что $n > r_{p_{e}} \geq A_{k}(1)$. Но по предположению $k \geq \alpha(n) \Rightarrow A_{k}(1) \geq A_{\alpha(n)}(1) \geq n$,
        первое неравенство по лемме $5.3$. Получили противоречие. Значит $level(e) < \alpha(n)$.
      \end{proof}
    \end{Lm}
    
    \begin{Lm}
      Для любого элемента $e$, не являющегося представителем своего множества, верно, что $1 \leq iter(e) \leq r_{e}$.
      \begin{proof}
        Так как $r_{p_{e}} \geq A_{level(e)}(r_{e})$, то $iter(e) \geq 1$.\\
        $r_{p_{e}} < A_{level(e) + 1}(r_{e}) = A_{level(e)}^{(r_{e} + 1)}(r_{e}) \Rightarrow iter(e) < r_{e} + 1 \Rightarrow iter(e) \leq r_{e}$.
      \end{proof}
    \end{Lm}
    
    Будем доказывать время работы СНМ методом амортизационного анализа.
    \begin{Def}
      Потенциал элемента. Определим для любого элемента $e$ величину $\varphi(e)$.\\
      $\varphi(e) = \begin{cases}
        \alpha(n) \cdot r_{e}, \text{если $e$ представитель своего множества}\\
        (\alpha(n) - level(e)) \cdot r_{e} - iter(e), \text{иначе}
      \end{cases}$\\
    \end{Def}
    
    \begin{Def}
      Потенциал. Для амортизационного анализа возьмем потенциал для $i$-ой операции $\varphi_{i} = \sum\limits_{e}{\varphi(e)}$.
    \end{Def}
    
    \begin{Lm}
      $\varphi_{0} = 0$, $\varphi_{i} \geq 0$.
      \begin{proof}
        Так как в начальный момент времени все элементы являются представителями своих одноэлементных множеств, то
        $\forall e: \varphi(e) = \alpha(n) \cdot r_{e} = \alpha(n) \cdot 0 = 0 \Rightarrow \varphi_{0} = \sum\limits_{e}{\varphi(e)} =
        \sum\limits_{e}{0} = 0$.\\
        Так как ранг и $\alpha$ величины неотрицательные, то $\alpha(n) \cdot r_{e} \geq 0$. Так как $level(e) < \alpha(n)$ (лемма $6.3$), то
        $(\alpha(n) - level(e)) \cdot r_{e} \geq r_{e}$, а так как $iter(e) \leq r_{e}$ (лемма $6.4$), то
        $(\alpha(n) - level(e)) \cdot r_{e} - iter(e) \geq r_{e} - iter(e) \geq 0$. Получили, что $\forall e: \varphi(e) \geq 0$. Значит
        $\varphi_{i} = \sum\limits_{e}{\varphi(e)} \geq 0$.
      \end{proof}
    \end{Lm}
    
    \begin{Thm}
      Для любой $i$-ой операции, имеющей тип $join$, амортизированное время работы $a_{i} = t_{i} + \Delta\varphi = \mathcal{O}(\alpha(n))$
      \begin{proof}
        Так как $\varphi_{i}$ зависит от $\varphi(e)$, который зависит от $r_{e}$, $level(e)$ и $iter(e)$, которые зависят от $r_{p_{e}}$, то
        потенциал изменится только у тех элементов, у которых изменился ранг или ранг предка, а также у тех элементов, которые перестали быть
        представителями своего множества. Так как операция $join(e_{1}, e_{2})$ может поменять ранг одного элемента, пусть $e_{1}$
        (то есть он стал представителем объединения множеств), а элемент $e_{2}$ перестал быть представителем своего множества, то
        $\varphi(e)$ мог поменяться у $e_{1}$, $e_{2}$ и тех элементов, у которых $p_{e} = e_{1}$ (обозначим множество таких элементов за $S$).\\
        Обозначим за $\varphi'(e)$, $level'(e)$ и $iter'(e)$ потенциал, порядок и характеристику порядка элемента $e$ после операции $join$ соответственно.
        Тогда $\Delta\varphi(e_{2}) = \varphi'(e_{2}) - \varphi(e_{2}) = 
        (\alpha(n) - level(e_{2})) \cdot r_{e_{2}} - iter(e_{2}) - (\alpha(n) \cdot r_{e_{2}}) = -level(e_{2}) \cdot r_{e_{2}} - iter(e_{2})$,
        так как $level$ неотрицательный, а $iter$ положительный (леммы $6.3$ и $6.4$), то $\Delta\varphi(e_{2}) < 0$.\\
        Если ранг $e_{1}$ остался прежним, то $\forall e \in S: \Delta\varphi(e) = 0$, так как $r_{e}$, $level(e)$ и $iter(e)$ остались прежними.\\
        Если ранг $e_{1}$ поменялся, то если для некоторого элемента $e \in S$\ $level(e)$ остался прежним, то $iter(e)$ не уменьшился, так как иначе бы
        это означало, что $r_{p_{e}}$ уменьшился, что противоречит тому, что он увеличился. Если $iter(e)$ не изменился, то $\varphi(e)$ остался прежним,
        так как величины от которых он зависит не изменились. Если $iter(e)$ уменьшился, то
        $\Delta\varphi(e) = \varphi'(e) - \varphi(e) = (\alpha(n) - level'(e)) \cdot r_{e} - iter'(e) - ((\alpha(n) - level(e)) \cdot r_{e} - iter(e)) =
        (\alpha(n) - level(e)) \cdot r_{e} - iter'(e) - (\alpha(n) - level(e)) \cdot r_{e} + iter(e) = iter(e) - iter'(e) < 0$.\\
        Если ранг $e_{1}$ поменялся, то если для некоторого элемента $e \in S$\ $level(e)$ тоже поменялся, то
        $\Delta\varphi(e) = \varphi'(e) - \varphi(e) = (\alpha(n) - level'(e)) \cdot r_{e} - iter'(e) - ((\alpha(n) - level(e)) \cdot r_{e} - iter(e)) =
        (\alpha(n) - level'(e)) \cdot r_{e} - iter'(e) - (\alpha(n) - level(e)) \cdot r_{e} + iter(e) = r_{e} \cdot (level(e) - level'(e))
        + iter(e) - iter'(e) \leq -r_{e} + iter(e) - iter'(e)$, так как $iter(e) \leq r_{e}$ (лемма $6.4$), то $\Delta\varphi(e) =
        -r_{e} + iter(e) - iter'(e) \leq -iter'(e) < 0$, так как $iter'(e) > 1$ (лемма $6.4$).\\
        Получили, что изменение потенциала у всех элементов, кроме $e_{1}$ неположительное.\\
        Если $r_{e_{1}}$ не изменился, то $\Delta\varphi(e_{1}) = 0$, иначе
        $\Delta\varphi(e_{1}) = \varphi'(e_{1}) - \varphi(e_{1}) = \alpha(n) \cdot (r_{e_{1}} + 1) - \alpha(n) \cdot (r_{e_{1}}) = \alpha(n)$.\\
        Получили, что $\Delta\varphi = \sum\limits_{e}{\Delta\varphi(e)} \leq \Delta\varphi(e_{1}) \leq \alpha(n)$. Но так как $t_{i} = \mathcal{O}(1)$,
        то $a_{i} = t_{i} + \Delta\varphi = \mathcal{O}(\alpha(n))$.
      \end{proof}
    \end{Thm}
    
    \begin{Thm}
      Для любой $i$-ой операции, имеющей тип $get$, амортизированное время работы $a_{i} = t_{i} + \Delta\varphi = \mathcal{O}(\alpha(n))$
      \begin{proof}
        Аналогично рассуждениям из теоремы $6.8$, потенциал меняется только у элементов на пути операции $get$, причем потенциал не увеличивается.
        $i$-ая операция $get$ работает пропорционально $w_{i} + x_{i} + 1$:
        \begin{itemize}
          \item[1.] $w_{i}$ означает элементы $e$ на пути операции $get$, у которых $\Delta\varphi(e) < 0$.
          \item[2.] $x_{i}$ означает элементы $e$ на пути операции $get$ (кроме представителя множества), у которых $\Delta\varphi(e) = 0$.
          \item[3.] $1$. Некоторое константное количество действий. Сюда включено посещение представителя множества.
        \end{itemize}
        
        Если порядок некоторого элемента $e$ или характеристика порядка изменились, то они увеличились, так как
        величина $r_{p_{e}}$ увеличилась, но тогда аналогично рассуждениям из теоремы $6.8$ величина $\Delta\varphi(e) < 0$.\\
        Пусть $x_{i} > \alpha(n)$. Тогда так как количество различных порядков $\alpha(n)$ (лемма $6.3$), то $\exists e_{1}, e_{2}$
        на пути операции $get$, такие, что $level(e_{1}) = level(e_{2})$. Пусть $e_{2}$ находится ближе к представителю множества.
        Обозначим представителя множества за $R$, а $\varphi'(e)$, $level'(e)$ и $iter'(e)$ аналогично теореме $6.8$. Тогда
        $r_{R} \geq r_{p_{e_{2}}} \geq A_{level(e_{2})}(r_{e_{2}}) = A_{level(e_{1})}(r_{e_{2}}) \geq A_{level(e_{1})}(r_{p_{e_{1}}})$
        значит если $level'(e_{1}) = level(e_{1})$, то $iter'(e_{1}) > iter(e_{1})$, так как в этом случае $r_{p_{e_{1}}} \geq
        A_{level(e_{1})}^{(iter(e_{1}))}(r_{e_{1}}) = A_{level'(e_{1})}^{(iter(e_{1}))}(r_{e_{1}}) \Rightarrow r_{R} \geq
        A_{level(e_{1})}(r_{p_{e_{1}}}) = A_{level'(e_{1})}(r_{p_{e_{1}}}) \geq
        A_{level'(e_{1})}(A_{level'(e_{1})}^{(iter(e_{1}))}(r_{e_{1}})) = A_{level(e_{1})}^{(iter(e_{1}) + 1)}(r_{e_{1}})$.
        Получаем противоречие, так как у элемента $e_{1}$ величина $\Delta\varphi(e_{1}) < 0$. Значит
        $x_{i} \leq \alpha(n)$.\\
        Получаем, что величина $a_{i}$ пропорциональна $w_{i} + x_{i} + 1 + \Delta\varphi$, но сумма каждого элемента $e$, учтенного
        в $w_{i}$, со своим $\Delta\varphi(e)$ неположительна, а $x_{i} \leq \alpha(n)$, значит $a_{i} = \mathcal{O}(\alpha(n))$.
      \end{proof}
    \end{Thm}
    
    \begin{Thm}
      Суммарное время работы всех операций с СНМ пропорционально $(m + q) \cdot \alpha(n)$.
      \begin{proof}
        $\sum\limits_{i}{t_{i}} = \sum\limits_{i}{a_{i}} - \varphi_{m + q} + \varphi_{0}$. Но по лемме $6.7$
        величина $\varphi_{0} = 0$, а $\varphi_{m + q} \geq 0$, а значит
        $\sum\limits_{i}{t_{i}} = \sum\limits_{i}{a_{i}} - \varphi_{m + q} \leq \sum\limits_{i}{a_{i}}$, но
        сумма $\sum\limits_{i}{a_{i}}$ пропорциональна $(m + q) \cdot \alpha(n)$.
      \end{proof}
    \end{Thm}
    