17
правок
Изменения
Нет описания правки
<tex>r[x]</tex> {{---}} массив рангов.
===={get}====
get(x)
if p[x] != x
|}
Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex> , равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\frac{m}{n} \right ] \right )} \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.
===Анализ реализации с ранговой эвристикой===
Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку (итерированный логарифм<tex>\mathrm(\lg*n)</tex>).
Рассмотрим <tex> a </tex> операций <tex> \mathrm{union} </tex> и <tex> b </tex> операций <tex> \mathrm{get} </tex> (<tex> b > a </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
<tex> \mathrm{L(v)} </tex> — отец вершины,
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.
*<tex>\mathrm(\lg*n)</tex> - минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>
{{Утверждение
</center>
Во время <tex> \mathrm{get } </tex> после прохождения K ребер из второго класса <tex> \mathrm{R(v_1)} \geqslant x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.
Из выше сказанного и первого следствия второго утверждения получаем, что:
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]
== См. также ==
* [[СНМ (списки с весовой эвристикой)]]
* [[СНМ (наивные реализации)]]
== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296сстр 589. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)
