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

Хотя задачи о близости не обладают В-свойством, но с помощью второй леммы о сведении для оценки В-сложности мы можем воспользоваться теоремой 8.

Для базового множества, определяемого соотношениями (2.1), (2.3), (2.10)—(2.12), (2.18), (2.19) мы так же, как и в случае поиска идентичных объектов получаем константный в худшем случае алгоритм поиска.

Теорема 20. Если I = {X, V,pneari)первая задача о близости, Т — (F, Gi) — базовое множество, определяемое соотношениями (2.1), (2.3), (2.10)—(2.12), (2.18), (2.19), такое, что существует такое натуральное число т, что для любых различных у,у' Е V gh(y) ф = 9lmW), то 1 < Т(1,Т) Ц 2.

Доказательство. Пусть m — число, упомянутое в условиях теоремы. Пусть Х,... ,ХШ разбиение, задаваемое предикатом g и V{ = Х{ CV, г = l,m. По определению числа m для любого г € €{l,m} Vj ^ 1.

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

Рассмотрим ИГ U, построенный следующим образом. Возьмем вершину, которую объявим корнем ИГ. Выпустим из корня m ребер, объявим их переключательными и занумеруем подряд, начиная с 1. Припишем корню переключатель g}п. Для каждого i Е {1, т?г} конец ребра, исходящего из корня, с номером г обозначим Д. Для каждой записи у Е V вершину fig^y) объявим переключательной, припишем ей переключатель д*,у, выпустим из нее 2 ребра и занумеруем их 1 и 2. Конец ребра с номером 1 объявим листом и припишем ему запись у. После того как мы выполним эту операцию для всех записей из V, мы для каждого г Е (1, т} выполним следующее. Если |Щ = 0 и j(i) ф 0, то отождествляем вершину ft с листом, являющимся концом ребра с номером 1, исходящего из вершины Pjuy Если |Vi| = 1 и j (г) ф 0, то отождествляем конец ребра с номером 2, исходящего из вершины ft, с листом, являющимся концом ребра с номером 1, исходящего из вершины

Нетрудно видеть, что ИГ U Е U(I, Т) и для любого запроса х Е X T(U,x) ^ 2. Откуда сразу следует справедливость теоремы.

Тем самым теорема доказана.

Следствие 9. Если Тбазовое множество, определяемое соотношениями (2.1), (2.3), (2.10) —(2.12), (2.18), (2.19), такое, что для любой библиотеки V существует такое натуральное число т, что для любых различных записей У,у'€Уд1т{у)ф то для любого

натурального к

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