170
правок
Изменения
м
{{Определение
|definition=Динамическая оптимальность (Dynamic Opt)
}}
Если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных.
Время работы tango-дерева <tex>O(OPT dyn * log log n)</tex>
→Динамическая оптимальность
==Динамическая оптимальность==
{{Гипотеза
|statement=''Splay-'' деревья обладают динамической оптимальностью.То есть время если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных.Время работы ''splay-'' дерева <tex>O(OPT dyn)</tex>
}}
{{Утверждение
|statement=Существует некоторое гипотетическое гипотетически оптимальное дерево, которое на каждый запрос делает следующие вещи
# идет от корня до <tex>x_{i}</tex>
# делает какиекакое-то количество поворотов
}}
===Оценка снизу на динамический оптимум===
====Визуализация работы с гипотетически оптимальным динамическим двоичным деревом поиска====
Рассмотрим оси ключи от временисистему координат ключ -- время.
Поставим точки, которые соответствуют обращению по данному ключу в определенное время.
Можно показать, что <tex>OPT >= M</tex>(число запросов) + максимальное число независимых прямоугольников * 1/2
==Вторая нижняя оценка Уилберра (Wilber) ==
