Теория вычислительной сложности
В теории вычислительной сложности формируется пара , составленная из алгоритма А, предназначенного для решения системы задач S и , в частности, конкретной (индивидуальной) задачи s из семейства S.
Для любой пары сложность можно оценивать системой показателей, каждый из которых называют сигнализирующей функцией.
Наибольшее распространение получила сигнализирующая времени TA(S) , определяющая число шагов, которые необходимо проделать алгоритму А для решения индивидуальной задачи sS.
Для оценки эффективности алгоритма А на семействе задач S в теории вычислительной сложности используется верхняя оценка сигнализирующей времени
(17)
а для выбора алгоритма из заданного набора {A}, наиболее эффективного для решения задач S, минимальная оценка
(18)
Помимо сигнализирующей времени формируют следующие функции сложности:
сигнализирующая ёмкости - число ячеек оперативной памяти, необходимых для решения задачи sS алгоритмом А;
сигнализирующая колебаний (поворотов) - количество циклов в программе для реальной ЭВМ, которые изменяют типовую последовательность вычислений;
сигнализирующая режима - число обращений к долговременным запоминающим устройствам.
(17) и (18) применяются ко всем сигнализирующим функциям. Наибольшее значение в теории имеют сигнализирующая времени, которую называют вычислительной сложностью и обозначают в виде функции, пропорциональной параметрам задачи.
Различают задачи полиномиальной и экспоненциальной сложности:
O(n2), O(n3)
O(an), O(bnlogn) и т.п.
Для (1) относятся задачи а) перемножения двух матриц порядка n; б) о кратяайшем маршруте на графе с n вершинами.
Для (2) - экстремальные задачи комбинаторного типа и задачи теории графов.
Задачи, для решения которых разработаны алгоритмы полиномиальной сложности, относятся к классу P-сложных задач.
Задачи, для решения которых разработаны алгоритмы экспоненциальной сложности, относятся к классу NP-полных задач.
Класс задач P-сложности является подклассом NP-сложных задач.
В книге Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи», Мир, 1982
предложена классификация задач принятия решений.
Приведён список 300 NP-сложных задач. Этот подкласс характерен тем, что, если хотя бы для одной из них будет разработан алгоритм решения полиномиальной сложности, то аналогичные алгоритмы можно получить для всех NP-полных задач.
Основная ценность теории вычислительной сложности - глубокий анализ проблемы построения эффективных алгоритмов и наличие алгоритмов для решения конкретных задач.
