Константный в среднем алгоритм поиска

Пусть Лемма 14. Пусть 1*2(1) — функция, определенная выше, пусть k, т 6 N, пусть.

Доказательство. Если доопределить функцию Ьг (/) на положительную полуось числовой прямой, например следующим образом:

то полученная функция будет непрерывной и вогнутой. Дальнейшее доказательство полностью аналогично доказательству леммы 12, так как в нем использовалось только свойство непрерывности и вогнутости функции L (x).

Тем самым лемма 14 доказана.

Пусть G2 — множество предикатов, определяемое соотношениями (2.10), (2.11), (2.12), такое, что для любого натурального т разбиение Х,…, Х_т, задаваемое предикатом gтакое, что для любых таких г, j € {l, m}, что г < j и любых х' € Х{ и х" G Xj выполняется.

Пусть базовое множество.

где G и G"2 определяются соотношениями (2.1), (2.3), (2.10), (2.11), (2.12), (2.18).

Справедлива следующая теорема [30].

Теорема 19. Пусть I = (X, V, p_neari) — первая задача о близости, где V — к, Т — базовое множество, определяемое соотношениями (2.1), (2.3), (2.10), (2.11), (2.12), (2.18). (2.19), т — натуральное число, с — константа, определяемая соотношением (2.11), L₂ (I) — функция, определяемая соотношением (2.17). Тогда

В частности,.

котором достигается верхняя оценка, T (U) ^ 1 + ]log₂(fc + 1)[.

Доказательство. Построим граф по аналогии с графом (/?, из доказательства теоремы 13.

Возьмем вершину 0о и объявим ее корнем графа. Из 0о выпустим т ребер, припишем им числа от 1 до т, объявим Pq точкой переключения и припишем ей переключатель <7^(х).

Пусть Vi = Xi П V, Ц = |VS|, t = T7^.

Конец ребра с номером г обозначим /%.

Для всех г таких, что ф 0, выполним следующую процедуру. Выпустим из вершины Д бинарное сбалансированное дерево D{ высоты ] log₂(/" -f 1)[ и с 1{ + 1 концевыми вершинами.

Объявим все концевые вершины этого дерева ?>*, кроме последней (самой правой), листьями и сопоставим им слева направо в порядке возрастания элементы из V*.

Для произвольной внутренней вершины & дерева D, — введем понятия Vp и ур, определяемые так же, как и в первом дереве бинарного поиска.

Объявим все внутренние вершины дерева D, вершинами переключения и для каждой внутренней вершины р левому ребру, из нее выходящему, припишем 1, правому — 2, а самой вершине припишем переключатель рч,_у^(х).

Пусть i G {1,ш}. Обозначим j (i) такой номер, что j (t) > t, |Vj (j)| > > 0 и не существует j^f: Vy > 0 и j' > i и j' < j (i), т. e. j (i) — индекс ближайшего сверху непустого множества Vj. Если такого множества нет, то j (i) = 0.

Теперь для каждого дерева D{ самую правую концевую вершину дерева отождествим с самым левым листом дерева Dj (i), если j (i) ф 0.

Для каждого такого г, что 1{ = 0, вершину Д отождествим с самым левым листом дерева если j (i) ф 0.

Полученный граф и будет ИГ U

Доказательство того, что ИГ разрешает первую задачу о близости I = (X, V, p_neari), аналогично доказательству того, что ИГ U разрешает задачу поиска идентичных объектов.

Подсчитаем объем графа U

Поскольку каждое из D{ есть дерево, в котором полустепень исхода любой вершины равна 2, то в D{ будет ровно 2-(^+1)—2 ребра. Отсюда следует, что.

Подсчитаем сложность графа U

Рассмотрим произвольный запрос х 6 X. При = 0.

Если U > 0, то активные на запросе х вершины графа образуют единственную цепь, ведущую из корня к вершине с искомой записью или же к самой правой вершине последнего дерева D{. В этой цепочке не более 1 + ]log₂(/i + 1)[ переключательных вершин и, значит,.

Отсюда следует, что Т (С/^, х) ^ 1 + L^U).

Тогда как следствие леммы 14 и по аналогии с теоремой 13 доказывается утверждение теоремы 19.

Что и требовалось доказать.

Следствие 8. Если Т — базовое множество, определяемое соотношениями (2.10), (2.11), (2.1), (2.12), (2.3), (2.18), (2.19), А: — натуральное число, то

и при к —> оо

Аналогично решается вторая задача о близости.

Пусть.

Тогда по аналогии с тем, как это делалось в доказательстве теоремы 19, мы можем построить ИГ над базовым множеством Т, определяемым соотношениями (2.10), (2.12), (2.20)-(2.22), который будет решать вторую задачу о близости. Опишем этот ИГ, который будем обозначать поскольку он будет широко использоваться при построении ИГ, решающих другие задачи.

Возьмем вершину 0 $ и объявим ее корнем графа. Из 0о выпустим т ребер, припишем им числа от 1 до га, объявим 0о точкой переключения и припишем ей переключатель gln (x).

Пусть Vi = Х_{ П V, h = Vi, i = 17^.

Конец ребра с номером i обозначим Д.

Для всех i таких, что V{ ф 0, выполним следующую процедуру. Выпустим из вершины 0{ бинарное сбалансированное дерево высоты ]log₂(fj 4- 1)[ и с li + 1 концевыми вершинами.

Объявим все концевые вершины этого дерева Dj, кроме первой (самой левой), листьями и сопоставим им слева направо в порядке возрастания элементы из V{.

Для произвольной внутренней вершины 0 дерева Di обозначим.

где 0" — конец правого ребра, исходящего из 0.

Объявим все внутренние вершины дерева Di вершинами переключения и для каждой внутренней вершины 0 левому ребру, из нее выходящему, припишем 1, правому — 2, а самой вершине припишем переключатель д^_уУР(х).

Пусть г € {1,7тг}. Обозначим j (i) такой номер, что j (i) > 0 и не существует j': Vy > 0 и f < i и j' > jf (i), т. e. j (i) — индекс ближайшего снизу непустого множества Vj. Если такого множества нет, то j (i) = 0.

Теперь для каждого дерева Di самую левую концевую вершину дерева отождествим с самым правым листом дерева Dj^, если j (i) ф 0.

Для каждого такого г, что = 0, вершину Д отождествим с самым правым листом дерева Dj^, если j (i) ф 0.

Полученный граф и будет графом U^.

Доказательство того, что граф U^ разрешает вторую задачу о близости, аналогично доказательству того, что граф разрешает первую задачу о близости.

Примеры, приведенные в разделе 2.2, с таким же успехом могут служить примерами рассмотренных задач о близости.