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

Рассмотрим упорядоченную совокупность 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].