Стр. 24 - Основы алгоритмов и структур данных

22 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Алгоритм №3.
1 n x + = +∞ /*чтобы гарантировать выход из цикла, как в 2*/
for(i=1;xi<z;i++);
if xi = z <успех>
else <неудача>
Очевидно, при равновероятном обращении к ключам время успешного
поиска равно времени неуспешного поиска и равно О(n/2).
Мы выиграли в быстродействии неуспешного поиска, но проиграли при
успешном, так как вместо операции сравнения ключей на равенство z x
i = ,
происходит сравнение на неравенство z x
i ≥ , которое почти всегда будет
медленнее. Если обращение к одним ключам происходит заметно чаще, чем к
другим, целесообразно упорядочить таблицу по убыванию частот вероятностей,
так, чтобы часто искомые ключи оказались в начале.
4.3. Логарифмический поиск
Пусть задачу поиска в таблице из n ключей можно за некоторое время С
это const, не зависящее от n свести к задаче поиска в таблице из n/k ключей, где
k это const >1. В таком случае общее время поиска в таблице из n ключей
удовлетворяет рекуррентному соотношению:
t(n) = C +t(n/k),
которое имеет решение:
t(n) = n C
k log +b.
b – некоторая константа, которая определяется начальными условиями.
Методы поиска, основанные на таком подходе (идее редукции), называют
логарифмическим.
4.3.1. Логарифмический поиск в статических таблицах
Статическим называют таблицы, в которых включение и исключение
записей происходит настолько редко, что потерями времени на них можно
пренебречь и просто перестроить таблицу заново.