За каждую итерацию выполняется до четырех команд: два сравнения, одна операция увеличения и одна передача управления.

Для ускорения внутреннего цикла общим приемом является добавление в таблицу

специальных строк, которые делают необязательной явную проверку того, достиг ли указатель границ таблицы. Это можно сделать в алгоритме 13.1. Если перед поиском мы добавим искомое имя в конце таблицы, то цикл всегда будет завершаться отысканием вхождения ; таким образом, нам не нужно в цикле каждый раз делать проверку . В конце цикла проверка условия , выполняемая лишь однажды, говорит о том, является ли найденное вхождение истинным или специальным элементом таблицы. Это демонстрируется в алгоритме 2.

i 1while z x_i do i i+1if i n then{найдено: i указывает на z} else{не найдено}

Алгоритм 2. Улучшенный последовательный поиск

Улучшение алгоритма 1 будет наиболее очевидным, если мы перепишем алгоритм 13.2 в тех же близких к языку машины обозначениях, которые использовались раньше:

i 1 цикл: if z = x_i then goto возможно i i+1

goto циклвозможно: if i n then {найдено:i указывает на z} else{не найдено}

При каждой итерации выполняются лишь три действия вместо четырех, как это было в алгоритме 1. Таким образом, в большинстве вычислительных устройств цикл в алгоритме 2 будет выполняться гораздо быстрее, чем в алгоритме 13.1, и поскольку скорость цикла определяет скорость всей программы, такое же сравнение имеет место для двух программ.

Печально то, что фокус с добавлением в конец таблицы перед поиском удается, только если мы имеем прямой непосредственный доступ к концу таблицы. Это возможно, если таблица хранится в памяти с произвольным доступом, но невозможно в общем случае, когда используется связанное размещение или память с последовательным доступом.

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

i 1 while z > x_i do i i+1if z=x_i then{найдено:i указывает на z} else{не найдено}

Алгоритм 3.Последовательный поиск по таблице, хранимой в естественном порядке.

 

Лекция № 4

Логарифмический поиск в статических таблицах. Бинарный поиск. Оптимальные деревья бинарного поиска. Логарифмический поиск в динамических таблицах.

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

Мы говорим о логарифмическом времени поиска, как только возникает возможность за время , не зависящее от , последовательно свести задачу поиска в таблице, содержащей имен.

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

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

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

Бинарный поиск

Когда ячейки таблицы последовательно распределены в памяти с произвольным доступом и имена хранятся в таблице в их естественном порядке, возможен бинарный поиск - один из наиболее широко используемых методов поиска. Идея этого метода состоит в том, чтобы искать имя в интервале, крайними точками которого являются два заданных указателя (для "низа") и (для "верха"). Новый указатель (для "средней точки") устанавливается где-то около середины интервала, и либо с именем в этой ячейке сводит интервал поиска к одному из интервалов или . Если интервал становится пустым, поиск завершается безуспешно.

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

Бинарный поиск по идее прост, но с деталями условия завершения поиска нужно обращаться осторожно. Частные случаи и требуют пристального внимания в любой программе бинарного поиска. В алгоритме 13.4 эти случаи обрабатываются тем же кодом, что и в общем случае, и поучительно посмотреть, как это делается, проследив за выполнением алгоритма для и .

Алгоритм 4. Бинарный поиск имени в таблице , хранящейся в естественном порядке.

Корректность алгоритма 4 следует из утверждения, данного в комментарии в начале тела цикла. Он устанавливает, что если находится где-либо в таблице, то оно должно находиться в интервале ; иначе говоря, при нашем предположении, что имя появляется в таблице не больше одного раза, утверждается, что не встречается ни в интервале , ни в интервале . Это утверждение очевидно первый раз, когда мы входим в цикл при и , и непосредственно по индукции проверяется, что оно выполняется при каждом проходе через цикл. Когда мы выходим из цикла, то должно быть , и поэтому утверждение принимает вид и , откуда следует, что .