170
правок
Изменения
→Оценка снизу на динамический оптимум
}}
[[Файл:DariaPicture1.png|thumb|left|400px| 1) Запрос вершины 3 : вершина 3; 2) Запрос 2 : вершина 3 – вершина 1 – вершина 2; 3) Запрос 4 : вершина 3 – вершина 4
]]
|proof=
'''1. Фазовая диаграмма работы с деревом поиска обладает свойством древестности.'''
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.
Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.
[[Файл:DariaPicture2.png|400pxthumb|300px| t - наименьший общий предок х и у
]]
Если <tex>t = x</tex>, то есть <tex>x</tex> -- предок <tex>y</tex> в момент <tex>i</tex>-го запроса,
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
То есть во время <tex>i</tex>-го запроса <tex>y</tex> был в поддереве <tex>x</tex>, а во время <tex>j</tex>-го запроса <tex>x</tex> в поддереве <tex>y</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю, и мы обращались к <tex>y</tex>, следовательно есть точка на правой стороне нашего прямоугольника.
'''2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.'''
Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.
Построим из них декартово(!) дерево, где ключом будет ключ, а вспомогательным ключом – время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>
[[Файл:DariaPicture3.png|400pxthumb|300px| Построение декартова дерева
]]
Но тогда рассмотрим прямоугольник(мы обращались к <tex>x</tex>)
А когда-то мы обратимся к <tex>y</tex>
Если есть точка на левой стороне, то к <tex>x</tex> мы обратимся раньше, чем к <tex>y</tex> следовательно неверно, что приоритет <tex>x</tex> больше чем приоритет <tex>y</tex>
На левой стороне точек нет.
Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у <tex>x</tex>, но меньше <tex>y</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>y</tex>.
Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к <tex>y</tex>.
Если на верхней стороне есть точка <tex>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>y</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.
}}
Таким образом, мы получили какую-то ''offline '' оптимальность.
Рассмотрим наши запросы, отметим их точками, тогда время работы оптимального динамического дерева равно количество точек на диаграмме.
Получим нижнюю оценку на оптимум.
<tex>OPT(x) = omega(f) </tex>
<font color=green>Если что-то работает за <tex>''O(f * g)</tex>'', значит это работает не более, чем в <tex>''g</tex> '' раз хуже.</font>
Рассмотрим запросы.
