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

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

'''Модель сравнения''': задача может быть решена с помощью бинарного поиска за <math>\Theta(lg \; n)</math> сравнений. Существует множество работ по адаптивным границам, которые могут быть сублогарифмическими. Такие границы могут зависеть от расстояния между пальцами, рабочего множества, энтропии и т. д.

'''Бинарные деревья поиска''': поиск предков является одним из фундаментальных мотивов для бинарных деревьев поиска. В рамках этой ограничивающей модели можно рассчитывать на оптимальный (конкурентный) алгоритм. Попытки достичь этого описаны в работе ''O(log log n)-конкурентные бинарные деревья поиска (2004; Demaine, Harmon, Iacono, P˘atra¸scu)''.

Традиционно принято считать, что совокупность имеет вид <math>U = \{ 1, ..., 2^{\ell} \}</math>, т. е. мы имеем дело с <math>\ell</math>-битными целыми числами. Представление с плавающей точкой было разработано таким образом, что порядок сохраняется, когда значения интерпретируются как целые числа, поэтому любой алгоритм будет работать и для <math>\ell</math>-битных чисел с плавающей точкой.

Стандартное трансдихотомическое предположение состоит в том, что <math>b = \ell</math>, так что входное целое число представляется в виде слова. Из этого следует <math>b \ge lg \; n</math>.

'''Модель клеточного зонда''': это неоднородная модель, более сильная, чем пословная RAM-машина, в которой операции являются произвольными функциями от слов памяти (ячеек), которые уже были прозондированы. Таким образом, <math>t_q</math> подсчитывает только количество зондирований ячеек. Это идеальная модель с точки зрения нижних границ, поскольку она не зависит от операций, реализуемых конкретным компьютером.

Этот подход может имитировать модель клеточного зонда, когда mB = b, а mA – логарифм объема памяти. Тогда т < <math>t_q</math> и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда.