Викиконспекты - Вклад участника [ru]

СНМ (реализация с помощью леса корневых деревьев)

2012-06-09T14:37:12Z

BoyCoder:

==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где get будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

===Объединение по рангу===
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на 1.

===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''get'' становится двухпроходной.

===Псевдокод===
Для реализации СНМ будем поддерживать следующие массивы:

<tex>p[x]</tex> {{---}} массив "родителей".

<tex>r[x]</tex> {{---}} массив рангов.
====get====
get(x)
if p[x] != x
p[x] = get(p[x])
return p[x]

====union====
union(x, y)
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

==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''

{| class="wikitable" border = 1
|-
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''get'' || <tex>O(\log n)</tex> || <tex>O(\alpha(m, n))</tex>
|-
| ''union'' || <tex>O(1)</tex> || <tex>O(1)</tex>
|}
* m {{---}} общее количество операций

* n {{---}} полное количество элементов

* <tex>\alpha(m, n)</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).

Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с n элементами есть <tex>O(\log n)</tex>, а значит и время работы операции get является логарифмическим.

Будем доказывать данное свойство по индукции. Для k = 0, очевидно, в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.

===Функция Аккермана===

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:

<tex>A(m, n) = \begin{cases}
2^n, & m = 1 \\
2, & m > 1, n = 0 \\
A(m - 1, A(m, n - 1)), & m > 1, n > 0
\end{cases} </tex>

Таблица значений функции Аккермана:

{| class="wikitable" border = 1
|-
!<tex>m \backslash n</tex> !! 0 !! 1 !! 2 !! 3 !! 4 !! 5
|- style = "text-align = center"
| 1 || 1 || 2 || 4 || 8 || 16 || 32
|-
| 2 || 2 || 4 || 16 || 65536 || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
|-
| 3 || 2 || 16 || <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>
|-
| 4 || 2 || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|}

Функция, обратная функции Аккермана <tex>\alpha(m, n)</tex> равна минимальному <tex>i</tex> такому, что <tex>A \left (i, \left [\frac{m}{n} \right ] \right ) \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.

===Анализ реализации с ранговой эвристикой===

Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку(итерированный логарифм).
Рассмотрим <tex> a </tex> операций <tex> union </tex> и <tex> b </tex> операций <tex> get </tex> (<tex> b > a </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2a </tex>.
#Количество вершин ранга <tex> i \le {a \over 2^i} </tex>.

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}a) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T_2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / b
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/b+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / b
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2a) = O(\log^*a)
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2a) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/b
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/a \le \sum_v \limits x^{R(v)} /a
</tex>.</center>

Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a \le \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a
\le
\sum_{Rank=0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*x) + O(1) = O(\log^*x) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

==Ссылки==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]

== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)

Дискретная математика, алгоритмы и структуры данных

2012-06-09T14:10:50Z

BoyCoder:

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]

Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

= Первый семестр =

== Отношения ==
*[[Определение отношения]]
*[[Степень отношений]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Транзитивный остов]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[КНФ]]
*[[Полином Жегалкина]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]

== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Обратное преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]
*[[Неравенство Крафта]]
*[[Неравенство Макмиллана]]

== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера по объекту]]
*[[Получение объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]
*[[Правильные скобочные последовательности]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
*[[Производящая функция]]

== [[Динамическое программирование]] ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о расстоянии Дамерау-Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула Байеса]]
*[[Формула полной вероятности]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Ковариация случайных величин]]
*[[Дисперсия случайной величины]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Задача о двух конвертах]]

== Марковские цепи ==

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]

= Второй семестр =

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Саморасширяющийся массив]]
* [[Массив с увеличением/уменьшением размера]]
* [[Стек]]
* [[Очередь]]
* [[Список]]
* [[Персистентный стек]]
* [[Персистентный дек]]

== Приоритетные очереди ==

* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]

== Поисковые структуры данных ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Splay-дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Дерево ван Эмде Боаса]]
* [[Рандомизированное бинарное дерево поиска]]
* [[Список с пропусками]]

== Дерево отрезков ==

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеширование]]
* [[Открытое и закрытое хеширование]]
* [[Поиск свободного места при закрытом хешировании]]
* [[Хеширование кукушки]]
* [[Двойное хеширование]]
* [[Перехеширование. Амортизационный анализ]]
* [[Фильтр Блума]]
* [[Универсальное семейство хеш-функций]]

== Сортировка ==
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Сортировка вставками]]
* [[Сортировка подсчетом]]
* [[Сортировка подсчетом сложных объектов]]
* [[Сортировка кучей]]
* [[Цифровая сортировка]]
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-й порядковой статистики за линейное время]]
* [[Теорема о нижней оценке для сортировки сравнениями]]
* [[Быстрая сортировка]]

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]
* [[Вещественный двоичный поиск]]
* [[Целочисленный двоичный поиск]]

== Связь между структурами данных ==
* [[Связь между структурами данных]]

= Третий семестр =

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм A*]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Циркуляция потока]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

= Четвертый семестр =

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]

=== Суффиксный массив ===
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Цифровая сортировка]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== Задача о наименьшем общем предке ==
* [[Метод двоичного подъема]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
* [[Сведение задачи RMQ к задаче LCA]]

== Матроиды ==
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Жадный алгоритм поиска базы минимального веса]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Теорема Эдмондса-Лоулера]]
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]
==Теория расписаний==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[QpmtnCmax|<tex>Q|pmtn|C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q|pmtn, r_{i}|L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]

СНМ (реализация с помощью леса корневых деревьев)

2012-06-09T14:06:21Z

BoyCoder:

==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где get будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

===Объединение по рангу===
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на 1.

===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''get'' становится двухпроходной.

===Псевдокод===
Для реализации СНМ будем поддерживать следующие массивы:

<tex>p[x]</tex> {{---}} массив "родителей".

<tex>r[x]</tex> {{---}} массив рангов.
====get====
get(x)
if p[x] != x
p[x] = get(p[x])
return p[x]

====union====
union(x, y)
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

==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''

{| class="wikitable" border = 1
|-
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''get'' || <tex>O(\log n)</tex> || <tex>O(\alpha(m, n))</tex>
|-
| ''union'' || <tex>O(1)</tex> || <tex>O(1)</tex>
|}
* m {{---}} общее количество операций

* n {{---}} полное количество элементов

* <tex>\alpha(m, n)</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).

Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с n элементами есть <tex>O(\log n)</tex>, а значит и время работы операции get является логарифмическим.

Будем доказывать данное свойство по индукции. Для k = 0, очевидно, в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.

===Функция Аккермана===

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:

<tex>A(m, n) = \begin{cases}
2^n, & m = 1 \\
2, & m > 1, n = 0 \\
A(m - 1, A(m, n - 1)), & m > 1, n > 0
\end{cases} </tex>

Таблица значений функции Аккермана:

{| class="wikitable" border = 1
|-
!<tex>m \backslash n</tex> !! 0 !! 1 !! 2 !! 3 !! 4 !! 5
|- style = "text-align = center"
| 1 || 1 || 2 || 4 || 8 || 16 || 32
|-
| 2 || 2 || 4 || 16 || 65536 || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
|-
| 3 || 2 || 16 || <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>
|-
| 4 || 2 || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|}

Функция, обратная функции Аккермана <tex>\alpha(m, n)</tex> равна минимальному <tex>i</tex> такому, что <tex>A \left (i, \left [\frac{m}{n} \right ] \right ) \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.

===Анализ реализации с ранговой эвристикой===

Проведем анализ реализации с ранговой эвристикой.
Рассмотрим <tex> a </tex> операций <tex> union </tex> и <tex> b </tex> операций <tex> get </tex> (<tex> b > a </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2a </tex>.
#Количество вершин ранга <tex> i \le {a \over 2^i} </tex>.

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}a) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T_2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / b
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/b+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / b
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2a) = O(\log^*a)
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2a) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/b
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/a \le \sum_v \limits x^{R(v)} /a
</tex>.</center>

Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a \le \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a
\le
\sum_{Rank=0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*x) + O(1) = O(\log^*x) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

==Ссылки==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]

== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)

СНМ (реализация с помощью леса корневых деревьев)

2012-06-09T06:34:04Z

BoyCoder:

==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где get будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

===Объединение по рангу===
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на 1.

===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''get'' становится двухпроходной.

===Псевдокод===
Для реализации СНМ будем поддерживать следующие массивы:

<tex>p[x]</tex> {{---}} массив "родителей".

<tex>r[x]</tex> {{---}} массив рангов.
====get====
get(x)
if p[x] != x
p[x] = get(p[x])
return p[x]

====union====
union(x, y)
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

==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''

{| class="wikitable" border = 1
|-
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''get'' || <tex>O(\log n)</tex> || <tex>O(\alpha(m, n))</tex>
|-
| ''union'' || <tex>O(1)</tex> || <tex>O(1)</tex>
|}
* m {{---}} общее количество операций

* n {{---}} полное количество элементов

* <tex>\alpha(m, n)</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).

Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с n элементами есть <tex>O(\log n)</tex>, а значит и время работы операции get является логарифмическим.

Будем доказывать данное свойство по индукции. Для k = 0, очевидно, в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.

===Функция Аккермана===

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:

<tex>A(m, n) = \begin{cases}
2^n, & m = 1 \\
2, & m > 1, n = 0 \\
A(m - 1, A(m, n - 1)), & m > 1, n > 0
\end{cases} </tex>

Таблица значений функции Аккермана:

{| class="wikitable" border = 1
|-
!<tex>m \backslash n</tex> !! 0 !! 1 !! 2 !! 3 !! 4 !! 5
|- style = "text-align = center"
| 1 || 1 || 2 || 4 || 8 || 16 || 32
|-
| 2 || 2 || 4 || 16 || 65536 || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
|-
| 3 || 2 || 16 || <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>
|-
| 4 || 2 || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|}

Функция, обратная функции Аккермана <tex>\alpha(m, n)</tex> равна минимальному <tex>i</tex> такому, что <tex>A \left (i, \left [\frac{m}{n} \right ] \right ) \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.

===Анализ реализации с ранговой эвристикой===

Проведем анализ реализации с ранговой эвристикой.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>.
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex>.</center>

Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

==Ссылки==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]

== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)

Анализ реализации с ранговой эвристикой

2012-06-06T09:21:49Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>.
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex>.</center>

Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-06T09:17:10Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>.
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex>.</center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-06T09:16:12Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex>.</center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-06T09:15:17Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>.
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>.
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex>.</center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex>.</center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-06T09:10:20Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex> </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex></center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex></center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex></center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-06T09:02:28Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>
</center>

Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex> </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex></center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex></center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{log_{2}(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex></center>

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-05T11:41:26Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>
</center>

Для того, чтобы <tex> \log^*_x </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex> </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex></center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex></center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{log_{2}(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex></center>.

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-05T11:30:33Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>
</center>

Для того, чтобы <tex> \log^*_x </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex> </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex>Т_3</tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex>Т_3</tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex></center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex></center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{log_{2}(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex></center>.

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Анализ реализации с ранговой эвристикой

2012-06-05T11:28:38Z

BoyCoder:

Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.

Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>
#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта получаем требуемое.
}}

{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:

Для 0 равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}

Из последнего утверждения следует:

#<tex> R(v) \le \log_2(n) </tex>
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>

{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:

#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.

Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.

Амортизационная стоимость

<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.

В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:

<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>
</center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>
</center>

Для того, чтобы <tex> \log^*_x </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>

Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex> </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex>Т_3</tex>.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex>Т_3</tex>.

<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex></center>

Из второго следствия второго утверждения следует
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex></center>

При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{log_{2}(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex></center>.

Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]