Стр. 22 - Основы алгоритмов и структур данных

20 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Табличный порядок может совпадать и не совпадать с естественным
порядком. Ключи в таблице могут быть упорядочены или не упорядочены.
Алгоритмы, использующие факт упорядоченности в таблице, имеют
логарифмическое быстродействие.
Заметим, в таблице с каждым ключом связана некоторая дополнительная
информация, ради которой и осуществляется поиск по этому ключу.
Часто в этом случае удобно из ключей сформировать отдельную таблицу,
называемую индексной таблицей или индексным файлом.
В основной таблице записи никак не упорядочиваются, в индексной
таблице ключи упорядочиваются в линейном порядке. Это обеспечивает
быстрый поиск в индексной таблице. Каждый индекс в ней сопровождается
указателем на запись в основной таблице.
Для простоты рассуждения будем предполагать, что ключи в таблице не
повторяются. Кроме операции поиска над таблицей, как правило, выполняются
и другие операции: добавление новых элементов, удаление существующих,
сортировка, изменение, распечатка и так далее. Поэтому эффективность того
или иного метода поиска, то есть эффективность того или иного способа
организации таблицы следует оценивать с точки зрения эффективности и
частоты выполнения всех выполняемых над таблицей операций.
4.2. Последовательный поиск
Имена исследуются в том порядке, в котором они присутствуют в таблице
до тех пор, пока не будет найдено искомое имя.
Алгоритм №1.
for i = 1 to n
{
if x i = z
<успех>
}
<неудача>
Здесь и дальше x i - ключи в таблице, z – искомый ключ.
<успех> - последовательность действий, выполняемая, когда искомый
ключ найден, в том числе выход из процедуры поиска.
<неудача> - последовательность действий, выполняемая, когда искомый
ключ отсутствует в таблице.
Оцениваем быстродействие. На успешный поиск ключа xi требуется i
итераций ( n i ≤≤ 1 ). Таким образом, среднее время на поиск любого ключа - это