4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Материал из WEGA
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 14:28, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 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>. | ||
== Применение == | == Применение == | ||
| Строка 31: | Строка 31: | ||
Но хотя улучшить асимптотический результат для случайной последовательности операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как [[косое дерево]]. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным. | Но хотя улучшить асимптотический результат для случайной последовательности m операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как [[косое дерево]]. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным. | ||
За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время | За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время выполнения которого оптимально с поправкой на константный коэффициент. Слейтор и Тарьян [14] получили ту же границу без предварительного знания D. Также стоит упомянуть оптимальность, не зависящую от ключей [10], и дерево бинарного поиска со свободными поворотами [1]. | ||
| Строка 41: | Строка 41: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Недавно было предложено еще несколько вариантов 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)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени выполнения. | |||
== См. также == | == См. также == | ||
| Строка 50: | Строка 50: | ||
== Литература == | == Литература == | ||
Tango [ ] – первое O(loglogn)-конкурентное бинарное дерево поиска; его алгоритм основывается на предложенной Уилбером [ ] нижней границе. Использующие многие идеи Tango и деревьев со связыванием и отрезанием (деревьев Слейтора-Тарьяна) [14, 19], многократно скошенные деревья [21] обобщают структуру конкурентных алгоритмов, дополняя их операциями вставки и удаления. Заслуживают особого внимания такие работы, как Самонастраивающиеся бинарные деревья поиска (Слейтор и Тарьян), Нижние границы доступа к бинарным деревьям поиска в присутствии поворотов (Уилбер), В поисках динамической оптимальности (Демейн и коллеги) и Динамическое O( | Tango [6] – первое O(loglogn)-конкурентное бинарное дерево поиска; его алгоритм основывается на предложенной Уилбером [22] нижней границе. Использующие многие идеи Tango и деревьев со связыванием и отрезанием (деревьев Слейтора-Тарьяна) [14, 19], многократно скошенные деревья [21] обобщают структуру конкурентных алгоритмов, дополняя их операциями вставки и удаления. Заслуживают особого внимания такие работы, как Самонастраивающиеся бинарные деревья поиска (Слейтор и Тарьян) [14], Нижние границы доступа к бинарным деревьям поиска в присутствии поворотов (Уилбер) [22], В поисках динамической оптимальности (Демейн и коллеги) [6] и Динамическое O(log log n)-конкурентное бинарное дерево поиска (Ван и коллеги) [21]. | ||
