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

Нижняя граница сложности класса алгоритмов определяется не един­ственным образом. Например, 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}, где

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

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

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

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

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

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

ства а = 0, b = c = 1, d = n-2. После первого сравнения на протяже­нии всего выполнения алгоритма постоянно будут иметь место нера­венства Ъ^1,с^1.

Все сравнения, совершаемые при выполнении алгоритма V, мож­но разбить на типы, обозначаемые AA,AB,AC,AD, BB,BC,BD,CC, CD,DD, например: сравнение принадлежит типу АВ, если один из сравниваемых элементов берется из А, другой—из В, и т. д. Исходя из этого, можно выписать все возможные изменения четверки (а, Ь, с, d) под действием сравнений разных типов:

1, b, c, d + 1), 1, b, c, d + 1), 1, b, c + 1, d),

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