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

Пусть Лемма 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, pneari) — первая задача о близости, где V — к, Т — базовое множество, определяемое соотношениями (2.1), (2.3), (2.10), (2.11), (2.12), (2.18). (2.19), т - натуральное число, сконстанта, определяемая соотношением (2.11), L2 (I) — функция, определяемая соотношением (2.17). Тогда

В частности,

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

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

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

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

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

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

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

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

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

Пусть i G {1,ш}. Обозначим j(i) такой номер, что j(t) > t, |Vj(j)| > > 0 и не существует jf: 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,pneari), аналогично доказательству того, что ИГ U разрешает задачу поиска идентичных объектов.

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

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

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

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

Если U > 0, то активные на запросе х вершины графа образуют единственную цепь, ведущую из корня к вершине с искомой записью или же к самой правой вершине последнего дерева D{. В этой цепочке не более 1 + ]log2(/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$ и объявим ее корнем графа. Из выпустим т ребер, припишем им числа от 1 до га, объявим точкой переключения и припишем ей переключатель gln(x).

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

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

Для всех i таких, что V{ ф 0, выполним следующую процедуру. Выпустим из вершины 0{ бинарное сбалансированное дерево высоты ]log2(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, с таким же успехом могут служить примерами рассмотренных задач о близости.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >