Задача анализа алгоритмов

Вычислительные модели. Показатели эффективности алгоритмов, задача анализа алгоритмов. Время выполнения алгоритма для худшего и среднего случая.

Вычислительные модели

Алгоритмы не существуют сами по себе, они создаются для конкретного исполнителя, и при разработке алгоритма разработчик ориентируется на его возможности – доступные ресурсы, операции и стоимости их использования. Все эти факторы учитываются в так называемой вычислительной модели [10].

В теоретических исследованиях, когда основной интерес представляет доказательство конечности алгоритма и его правильности, рассматривают вычислительные модели, удобные для анализа (но не для программирования!), с которыми легче работать математикам. Одна из наиболее известных таких моделей - машина Тьюринга.

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

В модели с внешней памятью, кроме быстрой памяти ограниченного объёма, имеется также внешняя память, обращения к которой производятся значительно медленнее, а обмен данными идёт блоками фиксированного размера (страницами).

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

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

Показатели эффективности алгоритма

Под эффективностью алгоритма понимается рациональное использование ресурсов заданной вычислительной модели [10].

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

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

Иногда приходится рассматривать и другие показатели – например, объём сетевого трафика между клиентом и сервером и т.д.

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

Задача анализа алгоритмов

Основной задачей анализа алгоритма является получение зависимости того или иного показателя эффективности от размера входных данных (размера входа, размера задачи). Сразу возникает вопрос – как измерять размер входа? Это зависит от конкретной задачи. В одних случаях размером разумно считать число элементов на входе (например, поиск элемента в массиве или его сортировка). Иногда размер входа измеряется не одним числом, а несколькими (например, число вершин и число рёбер в графе). В некоторых случаях более естественно считать размером входа общее число бит, необходимое для представления всех входных данных. Последний способ рассматривается как основной в теории вычислений.

Зависимость времени выполнения алгоритма от размера задачи называется временнóй сложностью алгоритма, а зависимость необходимого размера памяти от размера задачи — пространственной (емкостной) сложностью алгоритма.