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



             

Последовательный поиск


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

n
. Для больших таблиц его не следует относить к методам быстрого поиска, поскольку последовательный поиск асимптотически гораздо медленнее других алгоритмов, описанных в этой лекции. Несмотря на его низкие асимптотические возможности, имеется ряд причин, по которым этот метод следует обсудить вначале. Во-первых, хотя идея его проста, он позволяет нам ввести важные понятия и методы, применимые к поиску вообще. Во-вторых, последовательный поиск является единственным методом поиска, применимым к отдельным устройствам памяти и к тем таблицам, которые строятся на пространстве имен без линейного порядка. Наконец, последовательный поиск является быстрым для достаточно малых таблиц и для больших таблиц, организованных иерархическим способом: более быстрый метод используется для исследования окрестности верхушки иерархии, а последовательный поиск – для подтаблицы на нижнем уровне иерархии.

Для последовательного поиска по таблице

T = \{ x_1,x_2,\ldots,x_n \}
мы предполагаем, что имеется указатель
i
, значение которого принадлежит отрезку
1 \leqslant i \leqslant n
или, возможно,
0 \leqslant i \leqslant n + 1
. Над этим указателем разрешается производить только следующие операции; первоначальное присваивание ему значения 1 или
n
(или, если удобнее, 0 или
n + 1)
, увеличение и /или уменьшение его на единицу и сравнение его с 0, 1,
n
или
n + 1
. При таких соглашениях наиболее очевидный алгоритм поиска в таблице
T
первого вхождения данного имени
z
имеет вид алгоритма 13.1. Здесь, как и во всех других алгоритмах поиска, изложенных в настоящей лекции, мы полагаем, что алгоритм останавливается немедленно по отыскании
z
или установлении, что
z
в таблице нет.

for
i = 1
to
n

do
if
z = x_i
then
\{
найдено:
i
указывает на
z\}

\{
не найдено:
z
не входит в
T\}


Алгоритм 13.1. Последовательный поиск

for
i = 1
to
n

do
if
z = x_i
then
\{
найдено:
i
указывает на
z\}

\{
не найдено:
z
не входит в
T\}

Рассмотрим некоторые аспекты эффективности последовательного поиска, начиная со стандартных методов программирования.


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