ЛЕКЦИЯ 14. Классы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачи

Кроме правильности и корректности алгоритма и программы важным фактором является – эффективность или сложность алгоритма, т.е. время выполнения T (n), n – входные данные. Нахождение T (n) для программы является сложной задачей. И обычно используют асимптотическую оценку этой функции, т.е. ее примерное поведение при больших n. Эту функцию сложности алгоритма обозначают O (n).

Сложность алгоритма – насколько быстро растет его трудоемкость с увеличением объема входных данных, или количество элементарных операций.

В настоящее время принято использовать виды оценки сложности вычисления (классы сложности) приведенные в табл. 13.

Таблица 13.

Классы сложности алгоритмов

Порядок от сложного к простому	Название класса сложности	Математическая формула	Примеры алгоритмов
	Факториальная	n!	Алгоритмы комбинаторики (сочетания, перестановки и др.)
	Экспоненциальная		Алгоритмы перебора
	Полиномиальная		Алгоритмы простой сортировки
	Линейный логарифм		Алгоритмы быстрой сортировки
	Линейная		Перебор элементов массива
	Логарифмическая		Бинарный поиск
	Константная	k	Обращение к элементу массива по индексу

k – константа, n – переменные (входные данные)