§ 15. Оптимальные алгоритмы

109

Добавим, что никакая сортировка не может иметь сложность T{n) по числу сравнений, допускающую оценку an log₂ n + o(n log n), a < 1 (в частности, оценку an log₂ n + O{n)),—это следует из того, что для всех достаточно больших n выполнено T{n)>n log₂ n - 2n.

Пример 14.3. Обратимся к задаче поиска места элемента в упо­рядоченном массиве длины n.

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

Доказательство. Любой алгоритм поиска места элемента в упо­ рядоченном массиве фиксированной длины n может быть изображен бинарным деревом. Число листьев такого дерева есть n + 1. Далее рассуждаем так же, как при доказательстве предложения 14.2. □

Пример 14.4. Рассмотрим задачу вычисления aⁿ с помощью умно­жений (пример 4.2). Будем считать n размером входа. Затраты будем измерять количеством умножений.

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

Доказательство. На каждом этапе алгоритма мы имеем вычис­ленный набор степеней

a^m\a^m\...,a^mk\ (14.1)

при этом на начальном этапе набор состоит из одного элемента a¹. Выполнив одно умножение, мы, очевидно, не можем увеличить мак­ симальный показатель m = max{m₁,m₂, ...,m_k} более чем вдвое. По­ этому если определить на наборах вида (14.1) функцию L, равную log₂ n - log₂ m, то в результате одного шага (одного умножения) эта функция не может уменьшиться больше чем на 1. В то же время зна­ чение этой функции на исходном наборе равно log₂ n, а на итоговом наборе она заведомо неположительна. □

§ 15. Оптимальные алгоритмы

Нижняя граница сложности класса алгоритмов определяется не един­ственным образом. Например, f(n) = 0 всегда является нижней гра­ницей, равно как и любая отрицательная функция. Чем больше най­денная нижняя граница, тем она нетривиальнее и ценнее. Сигналом о том, что мы не сможем построить нижнюю границу большую, чем

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

уже имеющаяся у нас нижняя граница f(n), может служить, напри­мер, наличие A е .s4, для которого T_A(n) = f(n). С такой ситуацией мы сталкиваемся в предыдущем параграфе в примерах 14.1 и 14.3. Извест­ный нам алгоритм поиска наименьшего элемента и алгоритм бинар­ного поиска места элемента в упорядоченном массиве имеет каждый сложность, совпадающую с найденной нижней границей. Эти алго­ритмы являются оптимальными в смысле следующего определения.

Определение 15.1. Пусть .s4 — класс алгоритмов решения неко­торой задачи. Пусть принято соглашение о том, в чем измеряются затраты алгоритмов и что считается размером входа, и пусть n—обо­значение размера входа. Алгоритм Aе .s4 называется оптимальным в j4, если T_A(n) является нижней границей сложности алгоритмов из j4.

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

Предложение 15.1. Функция f(n) = Г₂ ⁿ1 - 2 является нижней границей сложности алгоритмов одновременного выбора наибольшего и наименьшего элементов массива длины n c помощью сравнений.

Доказательство. Каждый этап выполнения произвольного алго­ритма V, основанного на сравнениях и предназначенного для поиска наибольшего и наименьшего элементов массива, может быть охарак­теризован четверкой ( A, B, C, D) подмножеств множества исходных элементов {x_г, x₂, ■ ■ ■, x_n}, где

65535. A состоит из всех тех элементов, которые вообще не сравнива­лись;

65535. B состоит из всех тех элементов, которые участвовали в некоторых сравнениях и всегда оказывались большими;

65535. C состоит из всех тех элементов, которые участвовали в некото­рых сравнениях и всегда оказывались меньшими;

65535. D состоит из всех тех элементов, которые участвовали в некото­рых сравнениях, иногда оказываясь большими, а иногда — мень­шими.

Пусть a, b,c,d — количества элементов множеств A, B, C, D соответ­ственно. Исходная ситуация характеризуется равенствами a = n, b = = c = d = 0. После завершения алгоритма должны выполняться равен-