Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности

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

Определение 16.1. Пусть .s4 — класс алгоритмов решения неко­торой задачи. Пусть принято соглашение о том, в чем измеряются затраты алгоритмов и что считается размером входа, и пусть n —обо­значение размера входа. Функция f (n) называется асимптотической нижней границей сложности принадлежащих .s4 алгоритмов, если для сложности T_A(n) любого A е^мы имеем T_A (n) = П(f (n)). (Ес­ли используются несколько параметров n ₁, n₂,..., n_k размера входа, то асимптотическая нижняя граница—это, соответственно, функция ар­гументов n ₁, n₂,..., n_k.) Алгоритм A е .s4 называется оптимальным по порядку сложности в .s4, если T_A(n) является асимптотической ниж­ней границей сложности алгоритмов из .s4.

Очевидно, что любая неотрицательная нижняя граница сложно­сти является и асимптотической нижней границей, и что любой оп­тимальный алгоритм является оптимальным по порядку сложности.

Ниже в примере 16.4 мы увидим, что может существовать несколько оптимальных по порядку сложности в .s4 алгоритмов. Однако сложно­сти таких алгоритмов оказываются величинами одного порядка.

Теорема 16.1. Пусть A,B&.s4 оптимальны по порядку сложности в.s4. Тогда T_A (n)=е(T_B (n)).

Доказательство. Так как алгоритм A оптимален по порядку слож­
ности, имеем T_B (n) = П (T_A (n)) или, что то же самое, T_A(n) = O(T_B(n)),
что вместе с T_A(n) = О(T_B (n)) (алгоритм B оптимален по порядку
сложности) дает T_A(n) = в(T_B (n)). □

§ 16. Асимптотические нижние границы

Укажем достаточное условие оптимальности алгоритма по поряд­ку сложности.

Теорема 16.2. Если функция f (n) является асимптотической ниж­ней границей сложности принадлежащих классу.s4 алгоритмов и если алгоритм A&.s4 таков, что T_A(n) = O{f(n)), то этот алгоритм оп­тимален в.s4 по порядку сложности и T_A (n) = 6(f (n)).

Доказательство. Для произвольного B ел? имеем T_B{n) = П(f (n)); учитывая, что T_A{n) = O{f{n)), получаем T_B{n) = П{T_A{n)), т.е. алго­ритм A оптимален по порядку сложности.

Из T_A (n)=П(f (n)) и T_A{n) = O{f{n)) получаем T_A{n) =в(f (n)). □

Пример 16.1. Из предложения 14.5 следует, что функция f (n) = = log₂ n является асимптотической нижней границей сложности ал­горитмов вычисления aⁿ с помощью умножений (эта функция даже является нижней границей в смысле определения 14.1). Для сложно­сти бинарного алгоритма вычисления aⁿ мы имеем T _RS(n) = O (log n) (см. пример 4.2). Из теоремы 16.2 теперь получаем:

Бинарный алгоритм возведения в степень является оптимальным по порядку сложности в классе алгоритмов вычисления aⁿ с помощью умножений.

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

Пример 16.2. Вопрос о существовании и построении эйлерова цикла данного ориентированного графа сформулирован в задаче 16. Остановимся на случае связного графа. Очевидно, что если избрать число ребер | E | в качестве размера входа, то | E | является нижней границей сложности класса всех алгоритмов построения эйлеровых циклов, так как, во-первых, любой эйлеров цикл содержит по опре­делению все ребра графа и на любое ребро уйдет по крайней мере одна операция, и, во-вторых, для любого натурального n существует граф с \E\ = n, содержащий эйлеров цикл. Поэтому тот алгоритм со сложностью O (| E |), который требуется дать в задаче 16, будет опти­мальным по порядку сложности.

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

116 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

которого имеет некоторый неотрицательный вес. Имеется в виду де­рево:

(a) которое охватывает все вершины данного графа,

(b) все ребра которого являются ребрами данного графа,

(c) которое среди всех деревьев, обладающих свойствами (a), (b), имеет минимальный суммарный вес ребер Ч

Будем считать, что граф не содержит кратных ребер. Пример гра­фа с соответствующим остовным деревом дан на рис. 19. Для постро­ения минимального остовного дерева из­вестны остроумные алгоритмы, например, алгоритм Р.Прима² с оценкой сложности

O (| E | + | V |log| V |). (16.1)

Рис. 19. Граф с припи­санными ребрам весами и его остовное дерево.

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

| V |(| V |-1)

|(| V

имеет полный граф, то оценка (16.1) имеет следствием оценку O (| V |²). С другой стороны, асимптотическая нижняя граница Г2(| V |²) для алгоритмов такого рода получается тривиально: эту оценку до­пускает число ребер полного графа, а на каждое ребро графа алго­ритм затрачивает по крайней мере одну операцию (он не может не принять в расчет вес какого-либо ребра).

Если использовать для входов алгоритмов построения остовного дерева размер \V\, то \V\² даст асимптотическую нижнюю границу сложности этих алгоритмов, и алгоритм Прима будет оптималь­ным по порядку сложности (его сложность, соответствующая этому размеру входа, есть 6(| V |²)).

^:См. [21, гл. 24].

² Этот алгоритм описан, например, в [21, разд. 24.2].

§ 16. Асимптотические нижние границы

Из этого примера видно, что само свойство оптимальности нахо­дится в зависимости от выбора размера входа ^г.

В следующем примере, касающемся сортировки массивов, рас­сматривается сложность в худшем случае по числу сравнений.

Пример 16.4. Аналогично тому, как это сделано в примере 16.1, мы получаем, что любая сортировка, сложность которой допускает оценку О (log п!), является оптимальной по порядку сложности. В силу формулы Стирлинга мы имеем п log₂ п = 0(log п!), откуда следует, что любая сортировка, сложность которой по числу сравнений допускает оценку 0(n log п), является оптимальной по порядку сложности.

Сортировка бинарными вставками и сортировка фон Неймана яв­ляются оптимальными по порядку сложности по числу сравнений.

(Позднее мы установим оценку O (n log n) и для сложности рекурсив­ной сортировки слияниями.) Эти сортировки имеют разные сложно­сти как функции от п: например, T _vN(5) = 9, Г_в(5) = 8. Но, повторим, их сложности являются величинами одного порядка при п—> <х>. Резюмируем наши наблюдения.

Предложение 16.1. Необходимым и достаточным условием опти­мальности сортировки по порядку сложности является справедли­вость оценки O (n log n) для сложности этой сортировки. Если для некоторой сортировки справедлива оценка O (n log n), то справедлива и оценка G(n log n).

Доказательство. Достаточность уже установлена выше. Оставша­
яся часть доказательства следует, например, из теоремы 16.1 и оп­
тимальности по порядку сложности сортировки бинарными встав­
ками. □

Заметим при этом, что для сортировок бинарными вставками и фон Неймана справедливо значительно более сильное утверждение, чем утверждение об их оптимальности по порядку сложности. Для их сложностей и сложности T _opt(n) оптимального алгоритма имеет место асимптотическая эквивалентность:

Т_в(п) ~ T_vN(n) ~ T _opt(n) ~ п log₂ п ~ log₂ п\.

Коснемся нижних границ пространственной сложности алгоритмов сортировки. Если из всех этих алгоритмов выделить класс таких, кото­рые используют для перемещения элементов обмены (<—>), а не присва-

¹ Этот пример сообщил автору Е. В. Зима.

118 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

ивания (:=), то для этого класса единственной нижней границей, если говорить о функциях, принимающих неотрицательные значения, будет тождественно равная нулю функция, так как существуют, например, пузырьковая сортировка, сортировки простыми и бинарными встав­ками, не использующие дополнительных переменных того типа, к ко­торому относятся элементы сортируемого массива. (То, что требуются переменные для хранения значений индексов элементов, несуществен­но при изучении алгебраической сложности сортировки.) Алгоритмы, использующие присваивания для перемещения сортируемых элемен­тов, не могут, естественно, обойтись без дополнительного места для хранения хотя бы одной величины того же типа, что и элементы сор­тируемого массива, и одной из нижних границ будет функция, тожде­ственно равная единице. Если рассматривать все алгоритмы сортиров­ки вместе, то вновь единственная неотрицательная целочисленная гра­ница— это 0. В соответствии с этим определяются как оптимальные, так и оптимальные по порядку сложности алгоритмы.

Для произвольного класса .s4 оптимальный по порядку сложности алгоритм может и не существовать: если .s4 содержит всего два ал­горитма A_г,A₂ и при этом A_г имеет низкую сложность при четных значениях целочисленного размера входа n и высокую — при нечет­ных, а A₂ — наоборот, то, очевидно, ни A_ъ ни A₂ не будут опти­мальными в .s4 по порядку сложности (представим себе, что T_A = = (1 + (-1) n) n, T_{A 2} = (1 - (-1) n) n). В то же время, если допустить, что T_A =(2+(-1) ⁿn, T_A =(2-(-1) n) n, то T_A (n) = е(T_A (n)) (обе функ-ции имеют порядок n), и это говорит о возможности существования оптимального по порядку сложности алгоритма при отсутствии оп­тимального.

Дата добавления: 2014-01-11