Анализ алгоритма

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

Каждое реальное вычисление характеризуется:

1. определенной длительностью, физическим временем выполнения (время);

2. объемом требуемой памяти, физическим пространством (емкость);

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

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

имеет порядок ,

если.

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

Другой важной характеристикой алгоритма является его емкость. Под емкостью принято понимать максимальный объем памяти, используемый при вычислении. Говоря о физическом пространстве, необходимом для алгоритма в общем случае, мы не можем определить его точно. Современная компьютерная техника предоставляет в распоряжение простого пользователя, такие объемы памяти, которые еще несколько лет назад казались недостижимыми. В этих условиях создается не совсем верное представление об определении затрат памяти, как излишней операции. Самый «быстрый» алгоритм решения задачи, требующий затрат памяти соизмеримых с предоставляемым объемом, в произвольном случае не может быть реализован на большинстве современных компьютеров. Определение емкости алгоритма тесно связано с условиями его реализации для конкретной ЭВМ и используемого языка программирования. С другой стороны, набор типов данных, используемых в реальных вычислениях, относительно постоянен. Среди скалярных величин это целочисленные типы, вещественные типы и строковые типы. Среди векторных величин это, в основном, массивы скаляров, объем которых определяется совокупным объемом соответствующих скаляров. Большинство языков программирования выделяет для хранения скалярных величин один и тот же объем памяти.

Рассмотрим усредненный объем памяти, необходимый для хранения базовых скалярных типов данных в байтах. Положим =2 (для целочисленных типов); =4 (для вещественных типов); = (для строковых типов, где максимальная длина строки). Массив, состоящий из элементов имеет размер , где размер скаляра.

Пусть алгоритм имеет систему входных данных . Кроме того, для решения задачи требуется система вспомогательных данных . Введем в рассмотрение величину равную усредненному объему памяти, необходимому для хранения всех величин, участвующих в вычислительном процессе.

Итак, мы рассмотрели основные характеристики алгоритма: время и емкость. Введение понятий временной сложности алгоритма и усредненного объема памяти, необходимого для реализации алгоритма, позволяет нам перейти к рассмотрению понятия эффективности алгоритма.

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

Таблица 1

	Временная сложность
(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)
время работы

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

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

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

Дата добавления: 2014-01-07