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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Пусть <tex>R(v)</tex> - ранг вершины,<tex>P(v)</tex> - отец вершины,<tex>L(v) </tex> - первой {{Утверждение |statement…»)
 
Строка 1: Строка 1:
−
Пусть <tex>R(v)</tex> - ранг вершины,<tex>P(v)</tex> - отец вершины,<tex>L(v) </tex> - первой  
+
Пусть union(v1,v2) - процедура слития двух множеств содержащих  v1,v2, а get(v) - поиск корня поддерева содержащего x. Рассмотрим n операций union и m операций get. Для удобства и без потери общности будем считать что у нас union принимает в качестве аргументов корни поддеревьев и (m>n), то есть (union(v1,v2) заменяем на union(get(v1),get(v2)). Тогда нам надо оценить стоимость операции get(v). 
 +
Обозначим <tex>R(v)</tex> - ранг вершины,<tex>P(v)</tex> - отец вершины,<tex>L(v) </tex> - самый первый отец вершины.  
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
−
 
+
<tex> R(P(v))>R(v) </tex>
 
|proof=
 
|proof=
−
Предположим на секунду, что <tex>\sum a_n^+</tex> сходится. Но <tex>a_n^- = a_n^+ - a_n</tex>. Тогда, по линейности рядов, начнёт сходиться и ряд <tex>\sum a_n^-</tex>. Тогда, по линености рядов, так как <tex>|a_n| = a_n^+ + a_n^-</tex>, начнёт сходиться и ряд <tex>\sum |a_n|</tex>. Противоречие.
+
Из  того как работает функция get следует:
 +
1.<tex> R(L(v))>R(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>
 
}}
 
}}

Версия 23:46, 7 марта 2011

Пусть union(v1,v2) - процедура слития двух множеств содержащих v1,v2, а get(v) - поиск корня поддерева содержащего x. Рассмотрим n операций union и m операций get. Для удобства и без потери общности будем считать что у нас union принимает в качестве аргументов корни поддеревьев и (m>n), то есть (union(v1,v2) заменяем на union(get(v1),get(v2)). Тогда нам надо оценить стоимость операции get(v). Обозначим [math]R(v)[/math] - ранг вершины,[math]P(v)[/math] - отец вершины,[math]L(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]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Анализ_реализации_с_ранговой_эвристикой&oldid=7756»