| НЕТ ВОЙНЕ
|
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
Антивоенный комитет России
|
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
|
Пусть [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] следует:
- [math] R(L(v))\gt R(v) [/math].
- Между [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] |
Из последнего утверждения следует:
- [math] R(v) \le \log_2(n) [/math].
- Количество вершин ранга [math] i \le {n \over 2^i} [/math].
| Теорема: |
Амортизационная стоимость [math] get = O(\log^{*}(n)) [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим некоторое число [math] x [/math].
Разобьем наши ребра на три класса:
- Ведут в корень или в сына корня.
- [math] R(P(v)) \ge x^{R(v)}[/math].
- Все остальные.
Обозначим эти классы [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] |
Ссылки
