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

Неустойчивость канонического эффекта по отношению к базовому множеству

Как и следовало ожидать, сложность задачи поиска существенно зависит от выбора базового множества. Причем часто можно получить весь спектр, начиная от перебора (как самого сложного) до алгоритмов, сложность которых практически совпадает с мощностной нижней оценкой. Этот тезис хорошо иллюстрируется на примере одномерной задачи интервального поиска и подтверждается теоремами 43-49. Такую же картину можно наблюдать и для задачи включающего поиска (результаты следствия 12 и теоремы 28, теорем 29, 30 и 31), для задачи поиска идентичных объектов (теоремы 12, 13) и для задач о близости (теоремы 18, 19). Аналогичная картина наблюдается и для остальных типов ЗИП, хотя результаты, подтверждающие этот тезис, не приводятся в данной работе.

Таким образом, можно сформулировать следующее утверждение.

Утверждение 1. Канонический эффект очень чувствителен по отношению к базовому множеству, при этом малые изменения базового множества могут привести к существенным изменениям сложности ЗИП.

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