ВУЗ:
Составители:
103
18. ПОИСК. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК
Рассмотрим вопросы накопления информации в памяти компьютера
и способы её быстрого извлечения. При этом главным образом будем
изучать простейшую задачу: поиск информации, сохранённой с конкрет-
ным идентификатором. Например, поиск f
(x) по заданному x в таблице
значений функции f или поиск перевода на английский язык некоторого
русского слова.
Пусть имеется набор из N записей, а задача состоит в нахождении
одной из них. Как и в случае сортировки предполагается, что каждая за-
пись включает в себя специальное поле, хранящее её ключ. При этом тре-
буется N различных значений ключа для того, чтобы каждый из них од-
нозначно идентифицировал связанную с ним запись. Набор всех записей
обычно именуется таблицей, файлом или базой данных.
Алгоритм поиска имеет так называемый аргумент K, а задача за-
ключается в нахождении записи, для которой K служит ключом. В ре-
зультате поиска может возникнуть одна из двух ситуаций: либо поиск
завершился успешно (уникальная запись, содержащая ключ K, найдена),
либо поиск окончился неудачно (запись с ключом K не найдена). После
неудачного поиска иногда требуется внести в таблицу новую запись, со-
держащую ключ K. Такой метод называется алгоритмом поиска и вставки.
Хотя целью поиска является нахождение информации, хранящейся в
записи, идентифицируемой по ключу K, для простоты будем рассматри-
вать алгоритмы, предназначенные для поиска K. После нахождения K
поиск связанной с ним информации становится тривиальной задачей,
зависящей от способа хранения этой информации. Поэтому будем счи-
тать задачу поиска выполненной в тот момент, когда найдём ключ K или
убедимся в его отсутствии.
Поиск обычно является наиболее «времяёмкой» составляющей мно-
гих программ, и замена плохого метода поиска хорошим может значи-
тельно увеличить скорость работы программы.
Методы поиска могут быть классифицированы несколькими спосо-
бами. Во-первых, можно разделить их на внутренний и внешний поиск
так же, как различают алгоритмы сортировки внутренней и внешней.
Во-вторых, возможно деление на статические и динамические ме-
тоды поиска. При этом статический поиск предполагает, что содержимое
таблицы остаётся неизменным, а главная задача заключается в уменьше-
нии времени поиска. Динамический поиск проводится в таблице, которая
часто изменяется путём вставки, а возможно, и удаления элементов.
Третья возможная классификация методов поиска зависит от того,
на чём они основаны: на сравнении ключей или на некоторых числовых
свойствах ключей.
Страницы
- « первая
- ‹ предыдущая
- …
- 101
- 102
- 103
- 104
- 105
- …
- следующая ›
- последняя »
