Математическая логика и теория алгоритмов. Стенюшкина В.А. - 79 стр.

мкость достигает 0 (n^2) (например, для упорядоченных массивов). По образ-
ному выражению Н.Вирта, «быстрая сортировка напоминает азартную игру, где
следует рассчитать, сколько можно позволить себе проиграть в случае невезе-
ния».

       4.3 Поиск

       Типичными примерами поиска служат работа со справочником, катало-
гом в библиотеке, таблицами.
       Пусть файл ϕ состоит из записей ϕ(1),…, ϕ(n) с ключами kµ(i) ,i=1..n, k –
некоторое значение. Рассматривается четыре вида простейших задач поиска:
       1) Требуется определить по крайней мере одну запись в µ имеющую k
своим ключом;
       2) Требуется определить все записи в µ, имеющие k своим ключом;
       3) Если в µ нет записей с ключом k, то добавить в µ новую запись;
       4)Включить в µ новую запись.
       Число k называют аргументом поиска, или запросом, задачи 1 и 2 – прос-
тым поиском, 3 и 4 – поиском со вставкой. Поиск в задачах 1 и 2 может быть
безрезультатным. В задачах 1-3 поиск может быть организован по выполнению
условия а ≤ kµ(i) ≤ b, где а и b – константы и других условий. Здесь, как и ран-
нее, под файлом будем понимать одномерный или двумерный числовой или
символьный массив, то есть вести поиск в одномерной или двумерной таблице.
Эффективность алгоритмов поиска зависит от организации исходной информа-
ции. В частности полезным предварительным преобразованием µ может ока-
заться сортировка.
       4.3.1 Просмотр всех подряд записей до получения решения задач 1-3 на-
зывается последовательным поиском.
       4.3.2 Бинарный поиск упорядоченного массива состоит в следующем.
Сначала К сравнивается со средним ключом в таблице. Результат сравнения
или приводит к решению задачи, или позволяет определить, в какой части мас-
сива продолжить поиск. Применяя этот принцип к «половинному» массиву, че-
рез не более чем log n сравнений, получается положительный или отрицатель-
ный ответ.
       4.3.3 Задача поиска в сети ставится следующим образом. Пусть задана
ориентированная сеть S= (Р, R, d), где Р – множество вершин, R – множество
дуг; d – функция, определенная на R со значениями в множестве действитель-
ных чисел. Иногда d(х, у) интерпретирует как длина дуги (х, у) ∈ R.
       Основными подзадачами в алгоритмах оптимизации на сетях являются:
       - определение всех дуг сети вида (х, у) для фиксированной вершины х ∈
Р, то есть определение всех выходов у для данного х;
       - определение всех дуг сети вида (у, х) для фиксированной вершины х ∈
Р, то есть определение всех входов у для данного х;