Просмотр исходного текста страницы Анализ реализации с ранговой эвристикой

{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
|+
|-align="center"
|'''НЕТ ВОЙНЕ'''
|-style="font-size: 16px;"
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

''Антивоенный комитет России''
|-style="font-size: 16px;"
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|-style="font-size: 16px;"
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
|}

Пусть  <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> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.

{{Утверждение 
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </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>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение 
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции: 

Для 0 равенство очевидно.
Ранг вершины станет равным <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> не пустой, теорема доказана. 
}}

== Ссылки ==

* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]