3.2. Нижние и верхние оценки временной сложности.

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

Подчеркнем, что для многих алгоритмов отмечается ситуация «редкости» крайних значений: только на относительно небольшом количестве сочетаний исходных данных реализуются близкие к верхним или нижним оценкам значения сложности. Поэтому интересно бывает отыскать некоторое «усредненное» по всем данным число операций (получить среднюю оценку временной сложности).

3.3. Эффективность вычислений

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

Речь идет о различии между полиномиальными и экспоненциальными алгоритмами.

Полиномиальным называется алгоритм, временная сложность которого выражается некоторой полиномиальной функцией «размера» задачи n.

«Размер» задачи – это объем входных данных, необходимых для ее решения.

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

Различие между указанными двумя типами алгоритмов становятся особенно заметными при решении задач большого размера.

В связи с этим, полиномиальные алгоритмы называют эффективными, а полиномиально решаемые задачи – легкорешаемыми.

3.4. Классы сложности (p, exp, np, npc).

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

Задача называется полиномиальной, т.е. относится к классу Р, если существует константа k и алгоритм, решающий эту задачу за время O(nk).

Преимущества задач класс Р:

-для большинства реальных задач из класса Р константа k меньше 6;

-класс Р обладает свойством естественной замкнутости (можно комбинировать полиномиальные алгоритмы, используя один в качестве «подпрограммы» другого и при этом результирующий алгоритм будет полиномиальным).

Класс EXP - это класс всех экспоненциальных задач.

Класс NР задача относится к классу NP, если ее решение, полученное некоторым алгоритмом, может быть полиномиально проверено

Очевидно, что любая задача, принадлежащая классу Р, принадлежит и классу NP, т.к. она может быть полиномиально проверена, при этом задача проверки решения может состоять просто в повторном решении задачи.

Задача называется NP-полной (принадлежит классу NP-полных задач, т.е. классу NPC), если выполнены два условия:

1) задача принадлежит классу NP,

2) к этой задаче полиномиально сводятся все задачи из класса NP.

Понятие NP-полноты основывается на понятии сводимости одной задачи к другой.

3.5. Трудно решаемая задача.

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