Сложноть алгоритмов. Временная и пространственная сложности алгоритмов. Полиномиальные и экспоненциальные алгоритмы

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

Зависимость времени работы алгоритма от числа его шагов и представляет собой ВСА. Таким образом, ВСА – это функция, которая каждой входной длине n ставит в соответствие максимальное по всем индивидуальным задачам длины (наихудший случай) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины.

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

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

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