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

Зависимость сложности задачи поиска от объема памяти более “плавная”, чем от базового множества. Эту зависимость можно наблюдать на примере задачи поиска идентичных объектов.

Как можно видеть из теоремы 13, при объеме памяти 2к мы имеем логарифмический поиск, а при увеличении объема до (2 + с)А; мы плавно снижаем среднее время поиска до 2 операций. Эта зависимость более наглядна в асимптотической записи в случае равномерной вероятности запросов, т. е. когда с = 1:

Эта формула “разумна” при 0 ^ т ^ к. Таким образом, в данной ситуации выигрыш по времени логарифмически зависит от приращения объема.

Как видно из теоремы 19 аналогичная ситуация наблюдается и с задачами о близости. Относительно плавная зависимость сложности ЗИП от объема памяти подтверждается и исследованиями, касающимися задачи о доминировании, но нс вошедшими в данную работу, и двумерной задачи интервального поиска, приведенными в разделе 4.3.

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

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

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