Глава 4

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

§ 14. Понятие нижней границы сложности

Хорошо известно, что существуют алгоритмически неразрешимые за­дачи. Но если даже задача алгоритмически разрешима, то возможно, что сложность каждого из алгоритмов ее решения будет в определен­ном смысле достаточно высокой.

Пример 14.1. Рассмотрим задачу поиска наименьшего элемента с помощью сравнений в массиве длины п. Для того чтобы иметь основания отсеять элемент массива как заведомо не являющийся наименьшим, необходимо, чтобы этот элемент участвовал хотя бы в одном сравнении и оказался большим. Мы должны отсеять п — 1 элемент, а в каждом сравнении ровно один элемент оказывается большим. Это означает, что потребуется не менее п — 1 сравнения.

Введем основное понятие этой главы.

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

Это определение имеет смысл как для сложности в худшем случае, так и для сложности в среднем. Далее в примерах этого и следующего параграфов мы рассматриваем сложность в худшем случае; к сложно­сти в среднем мы вернемся в § 17. Всюду будет рассматриваться вре-

§ 14. Понятие нижней границы сложности

107

менная сложность. Мы можем сформулировать обнаруженный при рассмотрении примера 14.1 факт следующим образом.

Предложение 14.1. Функция /(п) = п - 1 является нижней гра­ницей сложности алгоритмов поиска наименьшего элемента массива длины п с помощью сравнений.

(Иными словами, не существует такого алгоритма выбора наи­меньшего элемента массива длины п c помощью сравнений, слож­ность которого хотя бы для одного значения п была меньше чем п-1.)

В роли класса .s4 здесь выступает класс алгоритмов поиска наи­меньшего элемента массива с помощью сравнений. Если бы помимо сравнений были допустимы какие-то еще операции, то, возможно, п-1 уже не годилось бы в качестве нижней границы. Например, ес­ли было бы разрешено пользоваться операцией выбора наименьшего из нескольких элементов, то задачу можно было бы решить одной операцией.

Пример 14.2. Рассмотрим класс алгоритмов сортировки с помо­щью сравнений. Если алгоритм работает для массивов любой дли­ны, то, разумеется, можно рассмотреть этот алгоритм применитель­но к массивам некоторой фиксированной длины п. Любая сортировка с помощью сравнений может быть для каждого конкретного п изоб­ражена бинарным деревом. В корне и внутренних вершинах находят­ся выполняемые сравнения, в листьях выписаны результаты сортиров­ки. Априори в исходном массиве возможен любой порядок элемен­тов, поэтому дерево будет иметь п\ листьев. Если взять, например, сортировку простыми вставками, то при п = 2 ее можно изобразить деревом, представленным на рис. 18а. При п = 3 дерево принимает вид, показанный на рис. 18б. Сложность в худшем случае для каждо­го п равна высоте соответствующего дерева (напомним, что высотой листа называется число ребер в том единственном пути, который ве­дет от корня дерева к этому листу; высотой дерева называется мак­симум высот его листьев). Если высота некоторого бинарного дерева равна а, то, очевидно, оно содержит не более 2^h листьев (максималь­ное возможное число листьев достигается в случае полного бинарно­го дерева, которое имеет ровно 2^h листьев). Поэтому если Г(п)—это временная сложность некоторой сортировки сравнениями, то должно выполняться неравенство

2^г("^п!,

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

а) Гx-l <x₂Л 1/ \0

Сx₂ <x₃~Л 1/ \0

б) Гx_г <x₂^Л

x_ъ < xj J

1/ \0

x_ltx₂,x₃ Сx_г <x₃~Л

\/ \0

Сx₃ <x₂"\ x₂,x_t,x₃

1/ \0

x₁,x₃,x₂ x₃,x_ltx₂ x₃,x₂,x_l x₂,x₃,x_l

Рис. 18. Дерево сортировки простыми вставками для случаев а) n = 2 и б) n = 3.

откуда T(n) ^log₂ n!; так как значение T(n)—целое число (мы изме­ряем сложность числом сравнений), то T{n) ^ [log₂ n\]. Доказанное можно сформулировать в виде предложения.

Предложение 14.2. Функция f(n) = [log₂ n\] является нижней гра­ницей сложности алгоритмов сортировки массивов длины n c помо­щью сравнений.

Отсюда можно вывести, например, следующее предложение.

Предложение 14.3. Пусть сложность T{n) некоторой сортиров­ки по числу сравнений не превосходит nlog₂n + cn, где c —некото­рая константа. Тогда T{n) = n log₂ n + O{n) и, как следствие, T{n)~ ~ n log₂ n.

Доказательство. В силу предложения 14.2 и формулы (10.12) для всех достаточно больших n мы имеем T{n) ^ [log₂ nil > n log₂ n - 2n, и, следовательно, n log₂ n - 2n < T{n) s= n log₂ n + cn. Отсюда следует требуемое. □

Это позволяет, например, заключить, что для сложности по чис­лу сравнений сортировки фон Неймана имеет место оценка T_vN(n) = = n log₂ n + O{n) и асимптотическое равенство T_vN(n) ~ n log₂ n, — мы уже видели, что T_vN < n\log₂ n\<n log₂ n + n.