Поиск предков: различия между версиями

Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи в моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры.

Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время <math>t_q + O(S/n)</math>. Таким образом, помимо нахождения элемента за один запрос предка, обновления изменяют минимальную часть структуры данных.

Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда <math>S \ge n^{1 + \varepsilon}</math>, оптимальный компромисс для коммуникативных игр совпадает с (1). Заметим, что случай <math>S = n^{1 + o(1)}</math> практически устраняется при сведении к коммуникационной сложности, поскольку сообщения Алисы зависят только от lg S. Таким образом, нет асимптотической разницы между <math>S = O(n)</math> и, скажем, <math>S = O(n^2)</math>.

Подход к реализации деревьев слияния с инструкциями AC0 известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины <math>AC^0</math>? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций <math>AC^0</math>?

Можно ли сделать время обновления детерминированным при решении динамической задачи? В частности, можно ли реализовать поиск ван Эмде Боаса с быстрым детерминированным обновлением? Это очень интересная задача, находящая применение в детерминированных словарях [ ]. Кроме того, можно ли детерминированным образом обновлять узлы слияния за константное время? Атомарные кучи [11] достигают этого результата при поиске только среди <math>(lg \; n)^{\varepsilon}</math> элементов, а не <math>b^{\varepsilon}</math>.

Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить <math>t+u = o(t_q)</math>, сохранив при этом эффективное время запроса?