Реализация алгоритма

Как только алгоритм выражен, допустим, в виде последовательности шагов и мы убедились в его правильности, настает черед реализации алгоритма, т. е. написания программы для ЭВМ.

Этот существенный шаг может быть довольно трудным. Во-первых, трудность заключается в том, что очень часто отдельно взятый шаг алгоритма может быть выражен в форме, которую трудно перевести непосредственно в конструкции языка программирования. Например, один из шагов алгоритма может быть записан в виде, требующем целой подпрограммы для его реализации. Во-вторых, реализация может оказаться трудным процессом потому, что перед тем, как мы сможем начать писать программу, мы должны построить целую систему структур данных для представления важных аспектов используемой модели. Чтобы сделать это, необходимо ответить, например, на такие вопросы:

Каковы основные переменные? Каких они типов?

Сколько нужно массивов и какой размерности? Имеет ли смысл пользоваться связными списками? Какие нужны подпрограммы (возможно, уже записанные в памяти)?

Каким языком программирования пользоваться?

Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.

Другой аспект построения программной реализации - это программирование сверху-вниз. Объяснение этого понятия будет дано в разд. 2.1, а пока укажем, что программирование сверху-вниз - это подход к разработке и реализации, который состоит в преобразовании алгоритма в такую последовательность все более конкретизированных алгоритмов, что окончательный вариант представляет собой программу для ЭВМ.

Сделаем одно важное замечание. Одно дело - доказать правильность конкретного алгоритма, описанного в словесной форме. Другое дело - доказать, что данная машинная программа, предположительно являющаяся реализацией этого алгоритма, также правильна. Таким образом, необходимо тень тщательно следить, чтобы процесс преобразования правильного алгоритма (в словесной форме) в машинную программу «заслуживал доверия».

Советуем читателю снова рассмотреть алгоритм ETS в свете обсуждения в данном подразделе и постараться построить его по этапам, как было предложено, пока вы не получите машинную программу.

Анализ алгоритма и его сложности

Существует ряд важных практических причин для анализа алгоритмов. Одной из них является необходимость получения оценок или границ для объема памяти или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память - относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени, которое указывается на рабочей карте. Поразительно, скольким программистам приходится слишком дорогим способом выяснять, что их программа не может обработать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью карандаша и бумаги для того, чтобы избежать ненужных прогонов. Хороший анализ способен выявить узкие места в наших программах, т. е. разделы программы, на которые расходуется большая часть времени (см. упр. 1.3.16).

Существуют также важные теоретические причины для анализа алгоритмов. Хотелось бы иметь некий количественный критерий для сравнения двух алгоритмов, претендующих на решение одной и той же задачи. Более слабый алгоритм должен быть улучшен или отброшен. Желательно также иметь механизм для выявления наиболее эффективных алгоритмов и замены устаревших. Иногда невозможно составить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, в то время как другой лучше работает на каких-то специальных входных данных. Хотелось бы иметь возможность делать аналогичные выводы о сравнительных достоинствах двух алгоритмов.

Важно также установить абсолютный критерий. Когда можно считать решение задачи оптимальным? Иными словами, когда наш алгоритм настолько хорош, что невозможно (независимо от наших умственных способностей) значительно его улучшить?

Пусть А - алгоритм для решения некоторого класса задач, an - размерность отдельной задачи из этого класса. Во многих задачах в этой книге п - просто скаляр, равный числу вершин графа. В общем случае п может быть массивом или длиной вводимой последовательности. Определим (п) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т. д.), которые должен выполнить алгоритм А для реше- ния любой задачи размерности п. Будем пользоваться следующим критерием для оценки качества алгоритма А. Говорят, что алгоритм А полиномиальный, если /(п) растет не быстрее, чем полином от п, в противном случае алгоритм А экспоненциальный. Этот критерий основан на времени работы в худшем случае, но аналогичный критерий может быть также определен для среднего времени работы. «Экс-

периментальная» основа для этого критерия качества заключается в том, что, по-видимому, последовательные или параллельные машины более или менее способны воспринимать полиномиальные алгоритмы для больших задач, а на экспоненциальных алгоритмах они довольно быстро «задыхаются».

Следующее обозначение стандартно во многих математических дисциплинах, в том числе и в анализе алгоритмов. Функцию f{n) определяют как О lg{n)] и говорят, что она порядка g{n) для больших ft, если

lim = constant =#=0.

Это обозначается, как fin)=0[g{n)]. Функция h{n) является о[z(п)] для больших п, если

Эти символы произносятся соответственно, как «О большое» и «о малое». Интуитивно, если }{п) есть 0[g{n)], то эти две функции, по существу, возрастают с одинаковой скоростью при ft-oo. Если f{n) есть o[g{n)], то g{n) возрастает гораздо быстрее, чем f{n).

Пример.

(а) Полином /(ft)=2ft°+6ft*-f 6п®+18 есть О(п), так как

lim 2/г+С«*Ч-6/г"+1В .д

Он представляет собой о(я"), о{е") и о (2"). Действительно, он является «о малым» от любой функции, возрастающей быстрее, чем полином пятой степени.

(б) Функция f{n)=2" есть о{п\), так как

Однако 2" есть 0(2"+) и o(5-i).

(в) Функция /(ft)=1000Kft есть о{п).

Итак, алгоритм полиномиальный, если /л(г)=0[Pft(n)] или !а{п)~ =о1Рй(п)], где fft(n) - некоторый полином от переменной п произвольной фиксированной степени k. В противном случае алгоритм является экспоненциальным.

Конечно, хотелось бы провести возможно более точный анализ, т. е. знать как можно больше о функции /(я). Мы бы лучше представили себе действие алгоритма А, если бы знали, что /(ft)=2,5 -f 3,7 ft-5,2, чем если бы нам было известно только, что /(ft)=0(n). Такие детальные сведения об алгоритме могут быть получены только из конкретной реализации. Точные коэффициенты /(ft) в общем слу-