22
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Алгоритм №3.
1
n
x
+
= +∞
/*чтобы гарантировать выход из цикла, как в 2*/
for(i=1;x
i
<z;i++);
if x
i
= 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. Логарифмический поиск в статических таблицах
Статическим называют таблицы, в которых включение и исключение
записей происходит настолько редко, что потерями времени на них можно
пренебречь и просто перестроить таблицу заново.
1...,14,15,16,17,18,19,20,21,22,23 25,26,27,28,29,30,31,32,33,34,...106