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

Пусть [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]

Из того как работает функция get следует: 1.[math] R(L(v))\gt R(v) [/math] 2. Между [math] v [/math] и [math] P(v) [/math] существует путь вида : [math] v -\gt L(v) -\gt L(L(v)) ... -\gt P(v) [/math] Записав неравенство из первого пункта вдоль пути из второго пункта следует что [math] R(P(v))\gt R(v) [/math]

[math]\triangleleft[/math]

Утверждение:

[math] R(v)=i =\gt K(v) \ge 2^i [/math]

[math]\triangleright[/math]

Докажем по индукции: Для 0 равенство очевидное. Ранг вершины стает равным [math] i [/math] при сливании поддеревьев ранга i-1, отсюда следует: [math]K(v)\gt =K(v1)+K(v2) \ge 2^{i-1}+2^{i-1} \ge 2^i [/math].

[math]\triangleleft[/math]

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

1. [math] R(v)\lt = log_2(n) [/math]

2. Количество вершин ранга [math] i \lt = {n \over 2^i} [/math]

Теорема:

Амортизационная стоимость [math] get = O(log^{*}(n)) [/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим некоторое [math] x [/math] . Разобьем наши ребра на три класса: 1.Ведут в корень или в сына корня. 2.[math] R(P(v))\gt =x^R(v)[/math] 3. Все остальные. Обозначим эти классы [math] T1,T2,T3 [/math] Амортизированная стоимость[math] S= {\sum_{get} \limits} ({\sum_{u \in get,u \in T1} \limits 1} + {\sum_{u \in get,u \in T2} \limits 1} + {\sum_{u \in get,u \in T3} \limits 1} ) / m = O(1) + {\sum_{get} \limits}{\sum_{u \in get,u \in T2} \limits}/m+ {\sum_{get} \limits}{\sum_{u \in get,u \in T3} \limits}/m [/math] , где [math] {u \in get } [/math] означает что ребро [math] u [/math] было пройдено во время выполнения текущего [math] get [/math].

[math]\triangleleft[/math]