Сложность задач и нижние оценки.

Когда речь идет о конкретном алгоритме решения конкретной задачи, то целью анализа временной сложности этого алгоритма является получение оценки для времени в худшем или в среднем, обычно асимптотической оценки сверху O (g(n)), при возможности – и асимптотической оценки снизу W (g(n)), а еще лучше - асимптотически точной оценки Q (g(n)).

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

Одной из задач, для которых известна нижняя оценка временной сложности, является задача сортировки:

§ Дана последовательность из n элементов a₁,a₂,... a_n, выбранных из множества, на котором задан линейный порядок.

§ Требуется найти перестановку p этих n элементов, которая отобразит данную последовательность в неубывающую последовательность a_p(1),a_p(2),... a_p(n), т.е. a_p(i)≤a_p(i+1) при 1≤i<n.

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

Для этой задачи доказана нижняя оценка временной сложности W (nlog(n)) для ограниченной модели вычислителя типа «дерево решений» [4 п.8.1.], т.е. нет алгоритмов (в определенном классе), решающих эту задачу, лучше (по порядку). Пусть надо упорядочить последовательность, состоящую из различных элементов . Алгоритм, упорядочивающий с помощью сравнений, можно представить в виде дерева

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

Лемма Двоичное дерево высоты h содержит не более листьев. (индукция по .)

Теорема. Высота любого дерева решений, упорядочивающего последовательность из различных элементов, не меньше (Любое дерево решений имеет листьев, Согласно лемме высота такого дерева ).

Следствие. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочение последовательности из элементов тратится не меньше сравнений при некотором с>0 и достаточно большом .

Доказательство. Поскольку , то оценка снизу

Отметим, что алгоритмы, решающие эту задачу за такое время, известны, т.е. Q (nlog(n)) является асимптотически точной оценкой и для этой задачи и для этих алгоритмов ее решения.

В оценках временной сложности задач и алгоритмов их решения важное положение занимает метод сведения. Пусть у нас есть две задачи A и B, которые связаны так, что задачу A можно решить следующим образом:

1) Исходные данные к задаче A преобразуются в соответствующие исходные данные для задачи B.

2) Решается задача B.

3) Результат решения задачи B преобразуется в правильное решение задачи A.

В этом случае мы говорим, что задача A сводима к задаче B. Если шаги (1) и (3) вышеприведенного сведения можно выполнить за время O (t(n)), где, как обычно, n – «объем» задачи A, то скажем, что A t(n)-сводима к B, и запишем это так: A µ_t(n) B. Вообще говоря, сводимость не симметричное отношение, в частном случае, когда A и B взаимно сводимы, мы назовем их эквивалентными. Следующие два самоочевидных утверждения характеризуют мощь метода сведения в предположении, что это сведение сохраняет порядок «объема» задачи.

Утверждение 1. (Нижние оценки методом сведения).