ГЛАВА 1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ     

1.1. Анализ производительности алгоритмов

Анализируя алгоритм, можно получить представление о том, сколь­ко времени займет решение данной задачи при помощи данного ал­горитма. Для каждого рассматриваемого алгоритма мы оценим, на­сколько быстро решается задача на массиве входных данных длины N. Например, мы можем оценить, сколько сравнений потребует алгоритм сортировки при упорядочении списка из N величин по возрастанию, или подсчитать, сколько арифметических операций нужно для умножения двух матриц размером N х N.

Одну и ту же задачу можно решить с помощью различных алгорит­мов.   Анализ алгоритмов дает нам инструмент для выбора алгоритма.

Различные характеристики алгоритмов предназначены для сравне­ния эффективности двух разных алгоритма, решающих одну задачу. Поэтому мы никогда не будем сравнивать между собой алгоритм сор­тировки и алгоритм умножения матриц, а будем сравнивать друг с дру­гом два разных алгоритма сортировки.

Результат анализа алгоритмов — не формула для точного количе­ства секунд или компьютерных циклов, которые потребует конкрет­ный алгоритм. Такая информация бесполезна, так как в этом случае нужно указывать также тип компьютера, используется ли он одним пользователем или несколькими, какой у него процессор и тактовая частота, полный или редуцированный набор команд на чипе процес­сора и насколько хорошо компилятор оптимизирует выполняемый код. Эти условия влияют на скорость работы программы, реализующей ал­горитм. Учет этих условий означал бы, что при переносе программы на более быстрый компьютер алгоритм становится лучше, так как он работает быстрее. Но это не так, и поэтому анализ алгоритмов не учитывает особенностей  компьютера.

В случае небольшой или простои программы количество выполнен­ных операции как функцию от N можно посчитать точно. Однако в большинстве случаев в этом нет нужды. Разница между алгоритмом, который делает N + 5 операции, и тем, который делает N + 250 операции, становится незаметной, как только N стано­вится очень большим. Тем не менее, анализ алгоритмов начинается с подсчета точного количества операций.

В самой ранней работе по анализу алгоритмов определена вычисли­мость алгоритма в машине Тьюринга. При анализе подсчитывается число переходов, необходимое для решения задачи. Анализ простран­ственных потребностей алгоритма подразумевает подсчет числа ячеек в ленте машины Тьюринга, необходимых для решения задачи. Такого рода анализ разумен, и он позволяет правильно определить относитель­ную скорость двух алгоритмов, однако его практическое осуществление чрезвычайно трудно и занимает много времени. Сначала нужно стро­го описать процесс выполнения функций перехода в машине Тьюринга, выполняющей алгоритм, а затем подсчитать время выполнения — весь­ма утомительная процедура.

Другой, не менее осмысленный, способ анализа алгоритмов пред­полагает, что алгоритм записан на каком-либо языке высокого уров­ня вроде Pascal, С, C++, Java или достаточно общем псевдокоде. Особенности псевдокода не играют существенной роли, если он реализует основные структуры управления, общие для всех алгорит­мов. Такие структуры, как циклы вида for или while, механизм ветвле­ния вида if, case или switch, присутствуют в любом языке програм­мирования, и любой такой язык подойдет для наших целей. Всякий раз нам предстоит рассматривать один конкретный алгоритм в нем редко будет задействовано больше одной функции или фрагмен­та программы, и поэтому мощность упомянутых выше языков во­обще не играет никакой роли.

Роль входных данных в анализе алгоритмов также чрезвычайно велика, поскольку последовательность действий алгоритма определяется не в последнюю очередь входными данными.

Скажем, некоторые алгоритмы сортиров­ки могут работать очень быстро, если входной список уже отсортиро­ван, тогда как другие алгоритмы покажут весьма скромный результат на таком списке. А вот на случайном списке результат может оказаться противоположным.

Например, для того, чтобы найти наибольший элемент в списке из N элементов, можно воспользо­ваться следующим алгоритмом:

largest = list  [l]

for i = 2 to N do

if (list   [i]   >   largest)   then largest = list[i]

end if end  for