Как можно измерить сложность алгоритма?

· Термин сложность алгоритма может трактоваться по-разному. Сложность может определяться количеством принятых решений и разветвлений алгоритма. Однако это не отражает понятия сложности с точки зрения машины. Машина может выполнять самый запутанный набор инструкций с той же лёгкостью, что и серию последовательно расположенных команд.

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

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

Классы сложности алгоритмов: полиномиальные и неполиномиальные алгоритмы
Полиномиальные алгоритмы.

nПредположим, что f (n) u g (n) – это математические выражения. Тогда утверждение, что функция g (n) ограничивает функцию f (n), означает, что при возрастании аргумента n значение функции f (n) непременно окажется больше значения функции g (n) и будет оставаться большим при дальнейшем возрастании аргумента n. Другими словами, выражение «функция g (n) ограничивает функцию f (n)» означает, что график функции f (n)

для больших значений n находится над графиком функции g (n).

Будем говорить, что задача относится к полиномиальному типу, если она принадлежит классу O (f (n))=const*f(n), где функция f (n) либо сама является полиномом, либо ограничивается некоторым полиномом а const – произвольная константа. Совокупность всех задач полиномиального типа традиционно обозначается как Р. Утверждение о том, что задача относится к полиномиальному типу, связано со временем, необходимым на её решение. Задача, принадлежащая к Р может быть решена за полиномиальное время, или же, то же самое, имеет полиномиальное временное решение.

Неполиномиальные алгоритмы.

n Определение принадлежности задачи к множеству Р является достаточно важным моментом в программировании. Поскольку это тесно связано с существованием практического решения задачи. Задачи не принадлежащие к множеству Р, являются неполиномиальными. Такие задачи характеризуются крайне высоким временем выполнения даже при обработке умеренного объёма входных данных.

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

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

Дата добавления: 2015-07-11