Пусть [math] union(v1,v2) [/math] - процедура слития двух множеств содержащих [math] v1 [/math],[math] v2 [/math], а [math] get(v) [/math] - поиск корня поддерева содержащего [math] v [/math]. Рассмотрим [math] n [/math] операций [math] union [/math] и [math] m [/math] операций [math] get [/math]. Для удобства и без потери общности будем считать [math] union [/math] принимает в качестве аргументов корни поддеревьев и [math] m \gt n [/math], то есть [math] union(v1,v2) [/math] заменяем на [math] union(get(v1),get(v2)) [/math].
Тогда нам надо оценить стоимость операции [math] get(v) [/math].
Обозначим [math]R(v)[/math] - ранг вершины,[math]P(v)[/math] - отец вершины,[math]L(v) [/math] - самый первый отец вершины, [math] K(v) [/math] - количество вершин в поддерева корнем которого является [math]
v [/math]
| Утверждение: |
[math] R(P(v))\gt R(v) [/math] |
| [math]\triangleright[/math] |
|
Из того как работает [math] get [/math] следует:
1.[math] R(L(v))\gt R(v) [/math]
2. Между [math] v [/math] и [math] P(v) [/math] существует путь вида : [math] v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow ... \rightarrow P(v) [/math]
Записав неравенство из первого пункта вдоль пути из второго пункта следует что [math] R(P(v))\gt R(v) [/math] |
| [math]\triangleleft[/math] |
| Утверждение: |
[math] R(v)=i \Rightarrow K(v) \ge 2^i [/math] |
| [math]\triangleright[/math] |
|
Докажем по индукции:
Для 0 равенство очевидное.
Ранг вершины стает равным [math] i [/math] при сливании поддеревьев ранга i-1, отсюда следует:
[math]K(v) \ge K(v1)+K(v2) \ge 2^{i-1}+2^{i-1} \ge 2^i [/math]. |
| [math]\triangleleft[/math] |
Из второго утверждения следует:
1. [math] R(v) \le \log_2(n) [/math]
2. Количество вершин ранга [math] i \le {n \over 2^i} [/math]
| Теорема: |
Амортизационная стоимость [math] get = O(\log^{*}(n)) [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим некоторое число [math] x [/math] .
Разобьем наши ребра на три класса:
1.Ведут в корень или в сына корня.
2.[math] R(P(v)) \ge x^{R(v)}[/math]
3. Все остальные.
Обозначим эти классы [math] T1,T2,T3 [/math]
Амортизированная стоимость
[math]
S= {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T1} \limits 1} + {\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T3} \limits 1} ) / m
[/math],
где [math] {v \in get } [/math] означает что ребро начало которого находится в [math] v [/math] было пройдено во время выполнения текущего [math] get [/math].
Ребро [math] v [/math] эквивалентно вершине в которой оно начинается.
В силу того что [math]{\sum_{v:v \in get,v \in T1} \limits 1} = O(1) [/math] получаем:
[math] S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1/m [/math] .
Во время [math] get [/math] после прохождения K ребер из второго класса [math] R(v1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} [/math]
Из выше сказанного и первого следствия второго утверждения получаем что: [math] {\sum_{v:v \in get,v \in T2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n)) [/math]
Для того, чтобы [math] \log^*_x [/math] существовал необходимо, чтобы [math] x \gt e ^{ 1 /e } \approx 1,44 [/math]
Рассмотрим сумму [math]{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1~/m \lt {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1/n [/math]
Из первого утверждения и того что происходит сжатие путей следует [math] R(P(x))[/math] cтрого увеличивается при переходе по ребру из Т3.
Как максимум через [math] x^{R(k)} [/math] переходов ребро перестанет появляться в классе Т3.
[math] {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T3} \limits } 1/n \le \sum_v \limits x^{R(v)} /n [/math].
Из второго следствия второго утверждения следует
[math] {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n \le \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over 2^{Rank} n} [/math].
При [math] x \lt 2~[/math] : [math]{\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) [/math].
В результате [math] S=O(1)+O(\log^*(x))+O(1)=O(\log^*(x)) [/math].
В силу того что интервал [math] (1,45...2) [/math] не пустой теорема доказана. |
| [math]\triangleleft[/math] |
