17
правок
Изменения
Нет описания правки
<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
| ''<tex>\mathrm{union}</tex>'' || <tex>\mathrm{O(1)}</tex> || <tex>\mathrm{O(1)}</tex>
|}
Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n</tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.
|}
Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex>, равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\frac{m}{n} \right ] \right )} \geq geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.
===Анализ реализации с ранговой эвристикой===
Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку (итерированный логарифм <tex>\mathrm(\lglog^*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{union(v_1,v_2)} </tex> заменяем на <tex> \mathrm{union(get(v_1),get(v_2))} </tex>.
<tex>^*</tex><tex>\mathrm(\log^*n)</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>
Оценим стоимость операции <tex> \mathrm{get(v)} </tex>.
<tex> \mathrm{L(v)} </tex> — отец вершины,
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.
{{Утверждение
Из последнего утверждения следует:
#<tex> \mathrm{R(v)} \le leqslant \log_2a </tex>.#Количество вершин ранга <tex> i \le leqslant {a \over 2^i} </tex>.
{{Теорема
Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in \mathrm{get},v \in T_2} \limits} \le leqslant \mathrm{\log^*_x(\log_2a)} = \mathrm{O(\log^*a)}
</tex>.
</center>
<center><tex>
{\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{\mathrm{get}: in ~ this ~ \mathrm{get} ~ v \in T_3} \limits }
1/a \le leqslant \sum_v \limits x^{\mathrm{R(v)}} /a
</tex>.</center>
Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a \le leqslant \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a}
</tex>.</center>
<center><tex>
{\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a
\leleqslant
\sum_{Rank=0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}}
\leleqslant
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\leleqslant
{ 2 \over 2-x } = \mathrm{O(1)}
</tex>.</center>
