Методы программирования. Громов Ю.Ю - 106 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

106
Рассмотрим далее так называемый последовательный поиск, заклю-
чающийся в следующем. Начать с начала и продолжать до тех пор, пока не
будет найден искомый ключ, и затем остановиться. Эта процедура пред-
ставляет собой очевидный путь поиска и может служить отправной точкой
для рассмотрения множества алгоритмов поиска, поскольку они основаны
на последовательном поиске. Заметим, что за простотой последовательного
поиска скрывается ряд интересных, несмотря на их простоту, идей.
Алгоритм S. (Последовательный поиск.)
Дана таблица записей R
1
, R
2
, …, R
N
с ключами K
1
, K
2
, …, K
N
соответ-
ственно. Алгоритм предназначен для поиска записи с заданным ключом K.
Предполагается, что N ≥ 1.
S1. [Инициализация.] Присвоить i ← 1.
S2. [Сравнение.] Если K = K
i
, то успешное завершение алгоритма.
S3. [Продвижение.] Увеличить i на 1.
S4. [Конец файла?] Если
Ni
≤
, то вернуться к шагу S2. В противном
случае алгоритм заканчивается неудачно. ■
Отметим, что этот алгоритм может завершиться успешно (искомый
ключ найден) и неудачно (искомый ключ отсутствует), что характерно
для большинства алгоритмов поиска.
Анализ алгоритма S несложен. Время его выполнения составляет
(5C – 2R + 3) единиц времени и зависит от количества сравнений ключей
C, а также результата R (R = 1 при успешном окончании поиска и R = 0
при неудачном). Если при поиске успешно найден ключ K
i
= K, то полное
время работы составляет (5i + 1) u. Если поиск окажется неудачным, то
время работы – (5N + 3) u. Если все ключи поступают на вход алгоритма
с одинаковой вероятностью, то среднее значение C в случае успешного
поиска равно
2
1...21 +
=
+++ N
N
N
.
Данный алгоритм, несомненно, знаком всем программистам, это не
самая лучшая реализация последовательного поиска. При небольшом
изменении алгоритм выполняется существенно быстрее (если записей не
слишком мало).
Алгоритм Q. (Быстрый последовательный поиск.)
В данном алгоритме, по сравнению с алгоритмом S, имеется дополни-
тельное предположение о наличии фиктивной записи R
N+1
в конце файла.
Q1. [Инициализация.] Присвоить i ← 1 и K
N+1
← K.
Q2. [Сравнение.] Если K = K
i
, то перейти к шагу Q4.
Q3. [Продвижение.] Увеличить i на 1 и вернуться к шагу Q2.
Q4. [Конец файла?] Если i ≤ N, то алгоритм заканчивается успешно;
в противном случае – неудачно (i = N + 1). ■

Страницы