4551
правка
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Материал из WEGA
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 14:28, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) м (→Литература) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 25: | Строка 25: | ||
'''Теорема 2. (Алгоритм Tango является <math>O(log \; log \; n)</math>-конкурентным BST-алгоритмом [6]).''' | '''Теорема 2. (Алгоритм Tango является <math>O(log \; log \; n)</math>-конкурентным BST-алгоритмом [6]).''' | ||
Время | Время выполнения алгоритма Tango BST на последовательности S из m операций доступа составляет <math>O((OPT(S, T_0)) + n) * (1 + log \; log \; n))</math>. | ||
== Применение == | == Применение == | ||
| Строка 34: | Строка 34: | ||
За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время | За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время выполнения которого оптимально с поправкой на константный коэффициент. Слейтор и Тарьян [14] получили ту же границу без предварительного знания D. Также стоит упомянуть оптимальность, не зависящую от ключей [10], и дерево бинарного поиска со свободными поворотами [1]. | ||
| Строка 42: | Строка 42: | ||
Недавно было предложено еще несколько вариантов O(log log n)-конкурентных бинарных деревьев поиска [9, 21]. Стоит отметить такой пример, как многократно скошенные деревья [21]. В них понятие границы чередования обобщается, допуская операции вставки и удаления. Для многократно скошенных деревьев было сформулировано несколько теорем, аналогичных теоремам для косых деревьев [20, 21] – таких как лемма об операциях доступа и теорема о рабочем множестве. Ван [21] предположил, что многократно скошенное дерево является O(1)-конкурентным; это предположение также пока не доказано. | Недавно было предложено еще несколько вариантов O(log log n)-конкурентных бинарных деревьев поиска [9, 21]. Стоит отметить такой пример, как многократно скошенные деревья [21]. В них понятие границы чередования обобщается, допуская операции вставки и удаления. Для многократно скошенных деревьев было сформулировано несколько теорем, аналогичных теоремам для косых деревьев [20, 21] – таких как лемма об операциях доступа и теорема о рабочем множестве. Ван [21] предположил, что многократно скошенное дерево является O(1)-конкурентным; это предположение также пока не доказано. | ||
Задача нахождения o(log log n)-конкурентного сбалансированного бинарного дерева поиска тоже остается открытой. Было предпринято несколько попыток улучшить нижнюю границу [6, 7, 22], но ни одна из них не дала в результате более низкий коэффициент конкурентности. Даже в несбалансированной модели задача нахождения O(1)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени | Задача нахождения o(log log n)-конкурентного сбалансированного бинарного дерева поиска тоже остается открытой. Было предпринято несколько попыток улучшить нижнюю границу [6, 7, 22], но ни одна из них не дала в результате более низкий коэффициент конкурентности. Даже в несбалансированной модели задача нахождения O(1)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени выполнения. | ||
== См. также == | == См. также == | ||
