Вычислительная сложность алгоритма

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

Вычислительной сложностью алгоритма (или просто сложностью) назовем количество шагов выполняемых алгоритмом в худшем случае. Она является функцией от размерности задачи, представленной входными данными. Например, для графа, задаваемого списками инцидентности, размерность задачи представляется как пара (n, m). Сложность алгоритма определяется, как функция f, такая, что f (n, m) равно числу шагов алгоритма для произвольного графа с n вершинами и m ребрами.

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

Для сравнения скорости роста двух функций и будем использовать обозначения или . Будем говорить, что функция имеет порядок роста не более, чем функция , что обозначается , тогда и только тогда, когда существуют С = const и N > 0 такие, что

Будем говорить, что функция имеет порядок роста не менее, чем функция , что обозначается , тогда и только тогда, когда существуют С = const и N > 0, такие, что

Например, для функции

в силу принятых обозначений, можно записать, что или . В общем случае, если – многочлен степени k, то

Непосредственно из определения вытекают следующие свойства:

;

;

.