В этом и следующих разделах представлен ряд алгоритмов поис-
ка данных и сортировок, выполняемых на статических структурах
данных, так как это характерные операции логического уровня для
таких структур. Однако, те же операции и те же алгоритмы примени-
мы и к данным, имеющим логическую структуру таблицы, но физически
размещенным в динамической памяти или на внешней памяти, а также
к логическим таблицам любого физического представления, обладаю-
щим изменчивостью.
Объективным критерием, позволяющим оценить эффективность то-
го или иного алгоритма, является, так называемый, порядок алго-
ритма. Порядком алгоритма называется функция O(N), позволяющая
оценить зависимость времени выполнения алгоритма от объема пере-
рабатываемых данных (N - количество элементов в массиве или таб-
лице). Эффективность алгоритма тем выше, чем меньше время его вы-
полнения зависит от объема данных. Большинство алгоритмов с точки
зрения порядка сводятся к трем основным типам:
- степенные - O(N^a);
- линейные - O(N);
- логарифмические - O(logA(N)). (Здесь и далее запись вида
"logА" обозначает "логарифм по основанию А").
Эффективность степенных алгоритмов обычно считается плохой,
линейных - удовлетворительной, логарифмических - хорошей.
Аналитическое определение порядка алгоритма, хотя часто и
сложно, но возможно в большинстве случаев. Возникает вопрос: за-
чем тогда нужно такое разнообразие алгоритмов, например, сорти-
ровок, если есть возможность раз и навсегда определить алгоритм с
наилучшим аналитическим показателем эффективности и оставить
"право на жизнь" исключительно за ним? Ответ прост: в реальных
задачах имеются ограничения, определяемые как логикой задачи, так
и свойствами конкретной вычислительной среды, которые могут помо-
гать или мешать программисту, и которые могут существенно влиять
на эффективность данной конкретной реализации алгоритма. Поэтому
выбор того или иного алгоритма всегда остается за программистом.
В последующем изложении все описания алгоритмов даны для ра-
боты с таблицей, состоящей из записей R[1], R[2], ..., R[N] с
ключами K[1], K[2], ..., K[N]. Во всех случаях N - количество
элементов таблицы. Программные примеры для сокращения их объема
работают с массивами целых чисел. Такой массив можно рассматри-
вать как вырожденный случай таблицы, каждая запись которой состо-
ит из единственного поля, которое является также и ключом. Во
всех программных примерах следует считать уже определенными:
константу N- целое положительное число, число элементов в массиве;
константу EMPTY - целое число, признак "пусто" (EMPTY=-1);
тип - type SEQ = array[1..N] of integer; сортируемые последова-
тельности.