8.3. Вычислительная сложность

Трудоемкость алгоритма, или временнáя сложность, т. е. время, затрачиваемое на выполнение алгоритма, оценивается числом условных элементарных операций, которые необходимо выполнить при решении задачи. Естественно, эта величина зависит от объема исходных данных, который оценивается некоторым параметром. Например, для графа это может быть число вершин или число ребер. Трудоемкость алгоритма, таким образом, можно оценить некоторой функцией f(n), где п – натуральное число, выражающее объем исходных данных.

Принято писать f(n) = O(g(n)), где g(n)  некоторая конкретная функция от n, если найдется такая константа с, что f(n)  сg(n) для любого n  0. При этом употребляют такие выражения: «трудоемкость алгоритма есть O(g(n))» или «алгоритм решает задачу за время O(g(n))». Если трудоемкость не зависит от объема исходных данных, то для ее обозначения используется символ О(1). Алгоритм трудоемкости О(п) называют линейным. Алгоритм трудоемкости О(п^b), где b – константа (возможно, дробная), называется полиномиальным. Если g(n) является показательной функцией, например 2^п, то говорят, что алгоритм обладает неполиномиальной, или экспоненциальной, сложностью.

Оценка трудоемкости алгоритма позволяет судить о том, как влияет быстродействие вычислительной машины на время выполнения алгоритма. Пусть имеется пять алгоритмов, трудоемкость которых соответственно п, n logn, п², п³ и 2^п. Пусть условная элементарная операция, которая является единицей измерения трудоемкости алгоритма, выполняется за одну миллисекунду. В табл. 8.1, показано, какого размера задачи могут быть решены каждым из этих алгоритмов за одну секунду, одну минуту и один час. Из этой таблицы видно, например, что за одну минуту алгоритм с трудоемкостью п² решает задачу в шесть раз большую, чем алгоритм с трудоемкостью п³.

Следует, однако, иметь в виду, что трудоемкость, выражаемая большей степенью полинома, может иметь меньший множитель с из приведенного выше неравенства f(n)  сg(n). Точно так же сложность алгоритма, которая носит экспоненциальный характер, может иметь множитель, меньший, чем у полиномиальной сложности. При разработке компьютерных программ для решения практических задач важно знать, при каких значениях параметра п время выполнения экспоненциального алгоритма оказывается меньше, чем время выполнения полиномиального алгоритма, решающего ту же задачу.

Таблица 8.1

Связь трудоемкости алгоритма с максимальным размером

задачи, решаемой за единицу времени

Временнáя	Максимальный размер задачи
сложность	1 с	1 мин	1 ч
п	1000	6  104	3,6  106
п logn	140	4893	2,0  105
n2	31	244	1897
n3	10	39	153
2n	9	15	21

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

Таблица 8.2

Связь размера задачи, решаемой за заданное время,

с быстродействием вычислительной машины

Временнáя	Максимальный размер задачи
сложность	до ускорения	после ускорения
п	s1	10 s1
п logn	s2	 10 s2
n2	s3	3,16 s3
n3	s4	2,15 s4
2n	s5	s5  3,3

Иногда удается найти способы сокращения перебора благодаря некоторым особенностям конкретных исходных данных.

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