3.2.2. Временная и емкостная сложность алгоритмов.

Если дана задача, как найти для ее решения эффективный алгоритм? А

если алгоритм найден, как сравнить его с другими алгоритмами, решающими

ту же задачу? Как оценить его качество? Вопросы такого рода интересуют и

программистов-практиков и программистов-теоретиков.

Для оценки алгоритмов существует много критериев. Наибольший инте-

рес представляет порядок роста необходимых для решения задачи времени и

емкости памяти при увеличении входных данных. Обычно с каждой конкретной

задачей связывается некоторое число, называемое ее размером, которое вы-

ражает меру количества входных данных. Например, размером задачи умноже-

ния матриц может быть наибольший размер матриц-сомножителей. Размером

задачи о графах может быть число ребер данного графа.

Время, затрачиваемое алгоритмом, как функция размера задачи, назы-

вается временной емкостью этого алгоритма. Поведение этой сложности в

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

ной сложностью. Аналогично можно определить емкостную сложность и асимп-

тотическую емкостную сложность.

Именно асимптотическая сложность алгоритмов определяет в итоге раз-

мер задач, которые можно решить этим алгоритмом. Если алгоритм обрабаты-

вает входы размера n за время c*n^2, где c - некоторая постоянная, то

говорят, что временной сложность этого алгоритма есть O(n^2) (читается

"порядка n^2").

Следующий пример придаст предшествующим рассуждениям более конкрет-

ный характер. Допустим, имеется пять алгоритмов A1, A2, A3, A4, A5 со

следующими временными сложностями соответственно O(n), O(n*log(n)),

O(n^2), O(n^3), O(2^n). Здесь временная сложность - это число единиц

времени, требуемого для обработки входа размера n. Предположим, что вре-

менные сложности алгоритмов A1, A2, A3, A4, A5, в действительности равны

соответственно 1000*n, 100*n*log(n), 10*n^2, n^3 и 2^n. Тогда A5 будет

наилучшим для задач размера 2<=n<=9, A3 - для задач размера 10<=n<=58,

A2 - при 59<=n<=1024, а A1 - при n>1024. -

3.2.3. Алгоритмы полиномиальной сложности и np-полные алгоритмы.

Сколько времени должна требовать задача, чтобы ее сочли действи-

тельно трудной? Общепринято, что если задачу нельзя решить быстрее, чем

за экспоненциальное время, то ее следует рассматривать как безусловно

трудно разрешимую. В этой "схеме классификации" задачи, решаемые алго-

ритмами полиномиальной сложности, будут легко разрешимыми. Но нужно

иметь в виду, что хотя экспоненциальная функция (такая, как 2^n) растет

быстрее любой полиномиальной функции от n, для небольших значений n, ал-

горитм, требующий O(2^n) времени, может оказаться эффективнее многих ал-

горитмов с полиномиально ограниченным временем работы. Например, сама

функция 2^n не превосходит n^10 до значения n, равного 59. Тем не менее

скорость роста экспоненциальной функции столь стремительна, что задачу

нызывают трудно разрешимой, если у всех алгоритмов, решающих ее, слож-

ность по меньшей мере экспоненциальна.

В теории алгоритмов приводятся соображения, показывающие, что неко-

торый класс задач, а именно задач полных для недетерминированного поли-

номиального времени (называемых NP-полными), вероятно, содержит только

трудно разрешимые задачи. Этот класс включает в себя многие "класси-

ческие" задачи из комбинаторики (такие, как задачу о коммивояжере, о га-

мильтоновом цикле, задачу целочисленного линейного программирования).

Замечание. Ключевое понятие в теории NP-полных задач - недетермини-

рованная машина Тьюринга - рассматривается в курсе "Дискретная математи-

ка".