Анализ реализации с ранговой эвристикой — различия между версиями

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

Версия 06:55, 8 марта 2011

Пусть [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 ... -\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_{v \in get,v \in T1} \limits 1} + {\sum_{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 \in get,v \in T1} \limits 1} = O(1) [/math] получаем [math] S = O(1) + {\sum_{get} \limits} ~ {\sum_{v \in get,v \in T2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v \in get,v \in T3} \limits} 1/m [/math] .

После K ребер из второго класса [math] R(v1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} [/math]

Из выше сказанного и первого следствия второй леммы получаем что [math] {\sum_{v \in get,v \in T2} \limits} = 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 \in get,v \in T3} \limits} 1~/m \lt {\sum_{get} \limits} ~ {\sum_{v \in get,v \in T3} \limits} 1/n [/math] Из первого утверждения следует [math] R(P(x)) [/math] только увеличивается при переходе по ребру из Т3.

Как максимум через [math] x^{R(k)} [/math] переходов ребро перестанет появляться в классе Т3. [math] {\sum_{get} \limits}~ {\sum_{v \in get,v \in T3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T3} \limits } 1/n \lt \sum_v \limits x^{R(v)} /n \lt \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over n 2^{Rank}} [/math]. При [math] x \lt 2~~~{\sum_{get} \limits}~ {\sum_{v \in get,v \in T3} \limits} 1/n \lt { 2 \over 2-x } = = O(1) [/math]. В результате [math] S=O(1)+O(1)+O(1)=O(1) [/math].

В силу того что интервал [math] (1,44..2) [/math] не пустой теорема доказана.
[math]\triangleleft[/math]