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

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

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

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

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

имен, где

- константа. В этом случае время

, требующееся для поиска в таблице с

именами, удовлетворяет рекуррентному соотношению

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

где

определяется начальными условиями и коэффициент

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

до

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

до

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

, являются предположения о том, что пространство имен

линейно упорядочено и что сравнение двух имен

из

(для определения

есть элементарная операция, требующая постоянного количества времени, не зависящего от

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

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

Содержание раздела