Комбинаторные алгоритмы для программистов



             

Логарифмический поиск в статических таблицах


Мы говорим о логарифмическом времени поиска, как только возникает возможность за время

c
, не зависящее от
n
, последовательно свести задачу поиска в таблице, содержащей
n

имен, к задаче поиска в таблице, содержащей не более

\alpha n
имен, где
\alpha < 1
- константа. В этом случае время
t(n)
, требующееся для поиска в таблице с
n
именами, удовлетворяет рекуррентному соотношению

 t(n) = c + t(\alpha n),

решение, которого имеет вид

 t(n) = c\log _{1/\alpha } n + b,

где

b
определяется начальными условиями и коэффициент
c
при логарифме есть время, требуемое для уменьшения размера таблицы от
n

до

\alpha n
.

Самыми распространенными предположениями, которые дают возможность уменьшить размер таблицы от

n
до
\alpha {\text{ }}n

за время, не зависящее от

n
, являются предположения о том, что пространство имен
S
линейно упорядочено и что сравнение двух имен
x,y
из
S
(для определения
x < y,x = y,x > y)
есть элементарная операция, требующая постоянного количества времени, не зависящего от
n
. В результате время, необходимое для большинства логарифмических алгоритмов поиска,естественно измеряется числом сравнений (с тремя исходами) пар имен. Для некоторых алгоритмов, однако, более естественны сравнения с большим, но фиксированным числом исходов.

В этом разделе мы рассматриваем только статические таблицы, то есть таблицы, в которых включение и исключение либо не встречаются, либо так редки, что когда они появляются, строится новая таблица. Динамические структуры таблиц, допускающие логарифмическое время поиска, так же как и эффективные алгоритмы включения и исключения, обсуждаются в конце этой лекции. Для статических таблиц нужно обсудить лишь алгоритмы поиска и построения таблицы. Алгоритмы поиска достаточно просты, но некоторые из алгоритмов построения таблицы сложны. Такая ситуация возникает потому, что в случае статической таблицы разумно считать частоты обращения известными, и, может быть, стоит затратить существенные усилия на построение оптимальной таблицы – таблицы с минимальным средним временем поиска (относительно данных частот обращения). Алгоритмы построения таблиц и их анализ являются наиболее важными темами этого раздела.




Содержание  Назад  Вперед