4640
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Перейти к навигации
Перейти к поиску
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 11:48, 1 марта 2016
, 1 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), S = | Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), <math>S = s_1, s_2, s_3, s_4, ... s_m \;</math>. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута вершина <math>s_i \;</math>. По пути алгоритм может модифицировать поля в любой вершине и поворачивать любые ребра. Стоимость выполнения последовательности операций доступа определяется как количество затронутых вершин плюс число поворотов. | ||
Пусть A – любой алгоритм бинарного поиска. Обозначим за A(S) стоимость обработки последовательности S | Пусть A – любой алгоритм бинарного поиска. Обозначим за A(S) стоимость обработки последовательности S, а за <math>OPT(S, T_0) \;</math> – минимальную стоимость обработки последовательности S. Алгоритм A является T-конкурентным, если для всех возможных последовательностей S, <math>A(S) \le T * OPT(S, T_0) + O(m + n) \;</math>. | ||