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

Рассмотрим упорядоченную совокупность U и множество T <math> \subset</math> U, |T| = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть задан элемент <math>x \in U</math>, требуется найти предка x, т. е. <math>max \{ y \in T | y < x \}</math>. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Обозначим за <math>t_q</math> время запроса, а за <math>t_u</math> – время обновления.

'''Коммуникативные игры''': предположим, что у Алисы есть запрос ''x'', а у Боба – множество T. Они пытаются найти предка ''x'' в результате <math>\tau</math> раундов коммуникации, где в каждом раунде Алиса посылает <math>m_A</math> бит, а Боб отвечает с помощью <math>m_B</math> бит.

Внешняя память: единицей доступа является страница, содержащая B слов по <math>\ell</math> бит каждое. B-деревья решают задачу со временем запроса и обновления <math>O(log_B \; n)</math>; этого также можно достичь, не обращая внимания на значение B ''(см. [[B-деревья без явного задания параметров кэша]])''. Модель клеточного зонда с <math>b = B \cdot \ell</math> сильнее данной модели.

'''<math>AC^0</math>-RAM''': это вариант пословной RAM-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, неограниченные схемы объединения по входу. Это исключает умножение из стандартного набора операций.

Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна, когда эффективность особенно важна. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7].

Основываясь на длительной серии исследований, Петрашку и Торуп [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-машины AC0? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций AC0?

Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить tu = o(tq), сохранив при этом эффективное время запроса?