170
правок
Изменения
м
→Динамическая оптимальность
Время работы tango-дерева <tex>O(OPT dyn \cdot \log \log n)</tex>
==Динамическая оптимальность==
Рассмотрим для начала понятие динамической оптимальности. За {{Определение|definition=Если стоимость бинарного дерева поиска - <tex> OPTdyn O(n + OPT(S))</tex> обозначим для всей ключей от 1 до n, то дерево называется '''динамически оптимальным'''.Это свойство трудно показать.Неизвестно, есть ли какое-то динамически оптимальное online бинарное дерево поиска, и также неизвестно полиномиальное время для вычисления OPT(S) с точностью до константы.Обозначим время работы динамически оптимального дерева <tex>O(OPT_{dyn})</tex>.}}
{{Гипотеза
}}
===Модель динамически оптимального дерева===
Рассмотрим ключи <tex>1..n</tex> и запросы <tex>x_{1}..x_{n}</tex>, где <tex>x_{i} \in \{1..n\}</tex> {{---}} ключ, к которому мы обращаемся.
