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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 4 участников)
Строка 1: Строка 1:
Пусть  <tex> union(v1,v2) </tex> - процедура слития двух множеств содержащих <tex> v1 </tex>,<tex> v2 </tex>, а <tex> get(v) </tex> - поиск корня поддерева содержащего <tex> v </tex>. Рассмотрим <tex> n </tex> операций <tex> union  </tex> и  <tex> m </tex> операций  <tex> get </tex>. Для удобства и без потери общности будем считать <tex> union </tex> принимает в качестве аргументов корни поддеревьев и <tex> m > n </tex>, то есть <tex> union(v1,v2) </tex> заменяем на  <tex> union(get(v1),get(v2)) </tex>.
+
Пусть  <tex> union(v_1,v_2) </tex> процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
 +
а <tex> get(v) </tex> поиск представителя множества, содержащего <tex> v </tex>.
 +
Рассмотрим <tex> n </tex> операций <tex> union  </tex> и  <tex> m </tex> операций  <tex> get </tex> (<tex> m > n </tex>).
 +
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
 +
то есть <tex> union(v_1,v_2) </tex> заменяем на  <tex> union(get(v_1),get(v_2)) </tex>.
  
Тогда нам надо оценить стоимость операции <tex> get(v) </tex>.   
+
Оценим стоимость операции <tex> get(v) </tex>.   
Обозначим <tex>R(v)</tex> - ранг вершины,<tex>P(v)</tex> - отец вершины,<tex>L(v) </tex> - самый первый отец вершины, <tex> K(v) </tex> - количество вершин в поддерева корнем которого является <tex>  
+
Обозначим <tex> R(v) </tex> ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
v </tex>
+
<tex> L(v) </tex> отец вершины,
 +
<tex> K(v) </tex> количество вершин в поддереве, корнем которого является <tex> v </tex>.
  
 
{{Утверждение  
 
{{Утверждение  
 
|statement=
 
|statement=
<tex> R(P(v))>R(v) </tex>
+
<tex> R(P(v)) > R(v) </tex>
 
|proof=
 
|proof=
Из того как работает функция get следует:
+
Из принципа работы функции <tex> get </tex> следует:
1.<tex> R(L(v))>R(v) </tex>
+
#<tex> R(L(v))>R(v) </tex>.
 
+
#Между  <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
2. Между  <tex> v </tex> и <tex> P(v) </tex> существует путь вида : <tex> v -> L(v) -> L(L(v)) ... ->P(v) </tex>
+
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
Записав неравенство из первого пункта вдоль пути из второго пункта следует что <tex> R(P(v))>R(v) </tex> 
 
 
}}
 
}}
  
 
{{Утверждение  
 
{{Утверждение  
 
|statement=
 
|statement=
<tex> R(v)=i => K(v) \ge 2^i </tex>
+
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
 
|proof=
 
|proof=
 
Докажем по индукции:  
 
Докажем по индукции:  
Для 0 равенство очевидное.
+
 
Ранг вершины стает равным <tex> i </tex> при сливании поддеревьев ранга i-1, отсюда следует:
+
Для 0 равенство очевидно.
<tex>K(v)>=K(v1)+K(v2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
+
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
+
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
 
}}
 
}}
  
 +
Из последнего утверждения следует:
 +
 +
#<tex> R(v) \le \log_2(n) </tex>.
 +
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.
 +
 +
{{Теорема
 +
|statement=
 +
Амортизационная стоимость <tex> get = O(\log^{*}(n))  </tex>
 +
|proof=
 +
Рассмотрим некоторое число <tex> x </tex>.
 +
Разобьем наши ребра  на три класса:
 +
 +
#Ведут в корень или в сына корня.
 +
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
 +
#Все остальные.
 +
 +
Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.
 +
 +
Амортизационная стоимость
 +
 +
<center>
 +
<tex>
 +
S =  {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
 +
+
 +
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1}  ) /  m
 +
</tex>,
 +
</center>
 +
где <tex>  {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
 +
Ребро <tex> v </tex>  эквивалентно вершине, в которой оно начинается.
  
Из второго утверждения следует:
+
В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:
 +
 
 +
<center>
 +
<tex>
 +
S = O(1) +  {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~  {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
 +
</tex>.
 +
</center>
 +
 
 +
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge  x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.
 +
 
 +
Из выше сказанного и первого следствия второго утверждения получаем, что:
 +
<center>
 +
<tex> {\sum_{v:v \in get,v \in T_2} \limits}  \le \log^*_x(\log_2(n)) = O(\log^*(n))
 +
</tex>.
 +
</center>
 +
 
 +
Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.
 +
 
 +
 
 +
Рассмотрим сумму
 +
<center> <tex>
 +
{\sum_{get} \limits} ~  {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
 +
<
 +
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
 +
</tex>. </center>
 +
Из первого утверждения и в силу использования сжатия путей следует,
 +
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.
 +
 
 +
Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.
 +
 
 +
<center><tex>
 +
{\sum_{get} \limits}~  {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits  }
 +
  1/n \le \sum_v \limits x^{R(v)} /n
 +
</tex>.</center>
 +
 
 +
Из второго следствия второго утверждения следует:
 +
<center> <tex>
 +
{\sum_{get} \limits}~  {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le  \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
 +
</tex>.</center>
 +
 
 +
При  <tex> x < 2~</tex>:
 +
<center><tex>
 +
{\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)
 +
</tex>.</center>
 +
 
 +
 
 +
Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
 +
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
 +
}}
  
1. <tex> R(v)<= log_2(n) </tex>
+
== Ссылки ==
  
2. Количество вершин ранга <tex> i <= {n \over 2^i} </tex>
+
* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]

Текущая версия на 19:21, 4 сентября 2022

Пусть [math] union(v_1,v_2) [/math] — процедура объединения двух множеств, содержащих [math] v_1 [/math] и [math] v_2 [/math], а [math] get(v) [/math] — поиск представителя множества, содержащего [math] v [/math]. Рассмотрим [math] n [/math] операций [math] union [/math] и [math] m [/math] операций [math] get [/math] ([math] m \gt n [/math]). Не теряя общности, будем считать, что [math] union [/math] принимает в качестве аргументов представителей, то есть [math] union(v_1,v_2) [/math] заменяем на [math] union(get(v_1),get(v_2)) [/math].

Оценим стоимость операции [math] get(v) [/math]. Обозначим [math] R(v) [/math] — ранг вершины, [math]P(v)[/math] — представитель множества, содержащего [math] 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 \dots \rightarrow P(v) [/math].
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
[math]\triangleleft[/math]
Утверждение:
[math] R(v) = i \Rightarrow K(v) \ge 2^i [/math]
[math]\triangleright[/math]

Докажем по индукции:

Для 0 равенство очевидно. Ранг вершины станет равным [math] i [/math] при объединении поддеревьев ранга [math]i-1[/math], следовательно:

[math]K(v) \ge K(v_1) + K(v_2) \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] T_1, T_2, T_3 [/math].

Амортизационная стоимость

[math] S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1} + {\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \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 T_1} \limits 1} = O(1) [/math] получаем:

[math] S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m [/math].

Во время [math] get [/math] после прохождения K ребер из второго класса [math] R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} [/math].

Из выше сказанного и первого следствия второго утверждения получаем, что:

[math] {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n)) [/math].

Для того, чтобы [math] \log^*_x(\log_2(n)) [/math] существовал необходимо, чтобы [math] x \gt e ^{ 1 /e } \approx 1,44 [/math].


Рассмотрим сумму

[math] {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m \lt {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n [/math].

Из первого утверждения и в силу использования сжатия путей следует, что [math] R(P(x))[/math] cтрого увеличивается при переходе по ребру из [math] T_3 [/math].

Как максимум через [math] x^{R(k)} [/math] переходов ребро перестанет появляться в классе [math] T_3 [/math].

[math] {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits } 1/n \le \sum_v \limits x^{R(v)} /n [/math].

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

[math] {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \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]

Ссылки