Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

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

Теорема 14. Если I = (X, V, pid)задача поиска идентичных

объектов, Т — (F, G^)базовое множество, определяемое соотношениями (2.2), (2.4), (2.10), (2.12), такое, что существует такое натуральное число т, что для любых различных у, у1 6 V <7^(2/) Ф = glm(y'),mol^T(I,T)^2.

Доказательство. Рассмотрим ИГ U, построенный следующим образом. Возьмем вершину, которую объявим корнем ИГ. Пусть т — число, упомянутое в условиях теоремы. Выпустим из корня т ребер, объявим их переключательными и занумеруем подряд, начиная с 1. Припишем корню переключатель д^. Для каждой записи у € G V из конца ребра с номером д}п(у) выпустим предикатное ребро с предикатом /=,у, конец этого ребра объявим листом и припишем этому листу запись у. Понятно, что U разрешает ЗИП /, и для любого запроса х 6 X выполняется T(U,x) ^ 2. Следовательно, Т(/, Т) < 2. Но поскольку одно вычисление всегда надо сделать, то Т(/, Т) ^ 1.

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

Следствие 7. Если Т = (F, (7г) ~ базовое множество, определяемое соотношениями (2.2), (2.4), (2.10), (2.12), такое, что для любой библиотеки V существует такое натуральное число т, что для любых различных записей у, у1V д]п(у) ф д)п(у'), то для любого

натурального к выполнено 1 ^ T(k,Sid,^F) ^ Т(к, S^F) ^ 2.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы