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

Известно не очень много алгоритмов, оптимальных в смысле опреде­ления 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. Асимптотические нижние границы

115

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

Теорема 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(logn) (см. пример 4.2). Из теоремы 16.2 теперь получаем:

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

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

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

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

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

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

1. которое охватывает все вершины данного графа,

1. все ребра которого являются ребрами данного графа,

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

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

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

3

6

2

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

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

|V|(|V|-1)

|(|V

2

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

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

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

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