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

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

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

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

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

Предположим, что 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 – произвольная константа. Совокупность всех задач полиномиального типа традиционно обозначается как Р.Утверждение о том, что задача относится к полиномиальному типу, связано со временем, необходимым на её решение. Задача, принадлежащая к Р может быть решена за полиномиальное время, или же, то же самое, имеет полиномиальное временное решение.

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

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

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

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