Понятие вычислительной сложности

Пусть A – алгоритм решения некоторого класса задач, а n – размерность задачи этого класса, тогда вычислительная сложность алгоритма – это некоторая функция , отображающая размерность задачи в «математическое» время ее решения, то есть дающая оценку количества некоторых операций, необходимых для решения данным алгоритмом любой задачи данного класса как функции от n. Функция f_A(n) является критерием качества алгоритма с точки зрения возможных временных затрат. Эффективным является понятие полиномиальный алгоритм, у которого растет не быстрее, чем полином от n. Алгоритм, имеющий экспоненциальную сложность: , пригоден для решения задач ограниченной размерности. Такие задачи определяют принадлежащими к классу NP – non-polynomial.

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

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

Однако ориентация на худший случай нередко приводит к пессимистическим оценкам, которые могут привести к неправильному выбору используемого алгоритма. Более реалистичной является оценка в среднем. Для задач на графы такая оценка появляется при предположении, что граф – однородный с некоторой средней степенью вершин.