2.2. Сложность алгоритма

Различают меры сложности алгоритмов двух видов:

• статическая сложность, не зависящая от входных данных задачи;

• динамическая сложность, зависящая от входных данных задачи.

Типичным примером статической меры сложности алгоритма является длина программы, которая может определяться, например, количеством операторов языка программирования.

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

Для многих алгоритмов точные верхние или нижние оценки меры сложности неизвестны. Поэтому при анализе алгоритмов об их сложности судят по асимптотическому поведению числа элементарных операций в зависимости от параметров задачи.

Для сравнения скорости роста меры сложности алгоритмов удобно использовать следующее обозначение. Пусть и – две неотрицательные функции (меры сложности). Говорят, что , если существуют такие положительные константы c и N, что для всех . Например, справедливы соотношения: .

В теории сложности выделяют два фундаментальных класса алгоритмов.

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

2. Алгоритмы с экспоненциальной оценкой сложности. В этом случае алгоритм имеет сложность при некотором , и его называют экспоненциальным.

Задача коммивояжера, задача о ранце, задача об упаковке в контейнеры принадлежат к так называемому классу NP-полных задач. Всякую задачу, принадлежащую классу NP, можно решить за экспоненциальное время перебором всех возможных вариантов. Класс NP-полных задач характеризуется следующими свойствами:

• никакую NP-полную задачу не удалось решить никаким известным алгоритмом полиноминальной сложности;

• если будет найден полиноминальный алгоритм для какой-нибудь NP-полной задачи, то существуют и полиноминальные алгоритмы для всех NP-полных задач.

На основании этих свойств высказывается гипотеза, что ни для какой NP-полной задачи не может существовать полиноминального алгоритма. Однако доказать это пока не удалось.

2.3. Запись алгоритма

Запись алгоритмов, представленных в этом пособии, заимствована из книг , где используется упрощенный Паскаль.

Операторы упрощенного Паскаля записываются по правилам, принятым в языке Паскаль. В частности, составной оператор заключается в операторные скобки begin и end. В упрощенный Паскаль вводятся некоторые дополнительные операторы.

• Оператор цикла: for do P (для каждого элемента x из множества X выполнить оператор P).

• Условный оператор: if exists x, B(x) then P else Q (если существует элемент x, удовлетворяющий условию B(x), то выполнить оператор P, иначе выполнить оператор Q).

• Оператор (обмен значениями между x и y).

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

Список называется стеком, если в нем выделен элемент, называемый вершиной (будем считать, что в непустом стеке вершиной является последний элемент, а в пустом стеке вершина не определена), и заданы следующие две процедуры и функция:

• – втолкнуть вершину x в стек, т.е. получить список вида ;

• – вытолкнуть вершину непустого стека в переменную x. В результате выполнения этой процедуры список S принимает значение , а ;

• top(S) – значением этой функции является вершина стека.

Список называется очередью, если в нем выделены начало (элемент) и конец (элемент) и определены две процедуры:

• – втолкнуть x в конец очереди, т.е. получить список ;

• – исключить из непустой очереди начало и передать его в переменную x. После выполнения этой процедуры и .