Глава 1. Алгоритмы поиска

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

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

Существует две возможности окончания поиска: либо поиск оказался удачным, то есть позволил определить положение соответствующей записи, содержащей К; либо неудачным, то есть показал, что К не может быть найден ни в одной из записей. После неудачного поиска иногда желательно вставить в таблицу новую запись, содержащую К. Алгоритм, который делает это, называется поиском со вставкой.

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

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

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

Имеется таблица записей R₁,R₂,…,R_n (N≥1), снабжённых ключами K₁,K₂,…,K_n. Алгоритм предназначен для поиска записи с ключом К.

1. Установить начальное значение i=1;

2. Если K_i=K_, то алгоритм завершён (идти на п. 5), запись R_i – искомая;

3. Перейти к следующей записи: i=i+1;

4. Если i≤N, то перейти на шаг 2, иначе – искомой записи в таблице нет;

5. Конец алгоритма.

Время работы алгоритма зависит от количества сравнений. Пусть обращение к записям происходит с равной вероятностью . Тогда среднее число сравнений

; СКО числа сравнений ≈0,289N.

Для ускорения работы алгоритма применяется алгоритм Q (быстрый последовательный поиск) – предполагается, что в конце стоит фиктивная запись R_N+1.

1. Установка i=1, K_N+1=K;

2. Если K_i=K, то перейти к п.4, иначе

3. Перейти к следующей записи: i=i+1 и вернуться к п.2;

4. Если i≤N, то поиск прошёл удачно, в противном случае – неудачно (i=N+1);

5. Конец.

Ускорение работы алгоритма до 30% по сравнению с алгоритмом S и достигается за счёт удаления одного сравнения из цикла.

Алгоритм Т (последовательный поиск в упорядоченной таблице).

Имеется таблица записей R₁,R₂,…,R_n,, причём ключи упорядочены по возрастанию: K₁<K₂<…<K_N. Предполагается, что в конце таблицы расположена фиктивная запись R_N+1, ключ которой K_N+1>>К. Это позволяет избежать зацикливания при K> K_N.

Если значение К с равной вероятностью принимает все возможные значения, то в случае удачного поиска алгоритм Т не лучше алгоритма Q. Однако отсутствие нужной записи алгоритм Т позволяет обнаружить примерно в два раза быстрее.

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

До сих пор предполагалось, что с равной вероятностью может потребоваться поиск любого аргумента, однако часто такое предположение неправомерно.

Пусть ключ K_i будет разыскиваться с вероятностью p_i, причём p₁+p₂+…+p_N=1. Время удачного поиска при больших N пропорционально числу сравнений С, среднее значение которого будет минимальна при p₁≥p₂≥…≥p_N, то есть когда наиболее часто используемые записи расположены в начале таблицы.

Рассмотрим распределение