Асимптотические оценки решений рекуррентных неравенств

Рассмотренный метод оценивания решений рекуррентных нера­венств (25.2), (25.14) приводит к достаточно точным оценкам, но требует многоэтапной работы. Часто бывает достаточно получить описание роста решения в виде простой асимптотической оценки. В § 24 мы получили оценку (24.7), указав при этом, что для ее вывода не нужно определять численные значения коэффициентов, входящих в соответствующее частное решение ассоциированного рекуррент­ного уравнения. Этот путь приводит к ряду общих теорем. Для них в разных литературных источниках используются синонимичные на­звания «теорема о рекуррентном неравенстве», «основная теорема о рекуррентных оценках» и т. д.^г Мы приведем две теоремы такого рода.

Теорема 26.1 (о рекуррентном неравенстве, случай ^).Пусть неотрицательная вещественная функция f натурального аргумента удовлетворяет неравенству

и, если п = 1,

где и, v, w, d — неотрицательные вещественные числа, причем v + w ^ ^ 1; с — положительное вещественное число. Тогда

fo(n^dlogn), если d = log₂(v+w),
f(n)=\o{n^d), если d>log₂(v+w), (26.2)

^О(п^1о&^(,,+и0), если d<log₂(v+w).

Доказательство. Решение ассоциированного уравнения

u, еслиk=0,

(v + w)t(k - 1) + c(2^d)^k, если k > 0,

имеет вид

t(fc)=co(v+w)4(c₁fc+c₂)(2^d)^fc = c₀(2^lo&^⁺^)4(c₁fc + c₂)(2^d)^fc (26.3)

с некоторыми конкретными с₀, с_г, с₂, причем с_г Ф 0, если и только ес­ли 2^d = v +w, или, что то же самое, если d = log₂(v + w). Рассмотрим раздельно три случая.

¹ В литературе на английском языке — «master theorem» (мастер-теорема).

170 Глава 6. Рекуррентные соотношения и сложность алгоритмов

Случай d = log₂(v + w). Имеем t(k) = {c_гk + (c₀ + c₂))(2^d)^k. Для до­статочно больших значений k выполняется

t{k)<Ck{2^d)^k = Ck{2^k)^d,

где C—некоторое положительное число. Используя предложение 25.1, заключаем, что

f(n)<CГю_§2n1(2^2nУ.

Это даетf(n) = O(n^d log n).

Случай d>log₂(v + w). Имеем t(k) = c₀(v + w)^k + c₂(2^d)^k. Для до­статочно больших значений k будем иметь

t{k)<C{2^d)^k = C{2^k)^d,

где C — некоторое положительное число. Аналогично предыдущему случаю с помощью предложения 25.1 получаем f{n) = O{n^d).

Случай d<log₂(v+w). Вновь имеем t{k) = c₀(v +w)^k + c₂(2^d)^k, но теперь для достаточно больших значений k будем иметь

t(k) < C(v + w)^k = C(2^log2(v+w))^k = C(2^k)^log2(v+w),

где C — некоторое положительное число. С помощью предложения
25.1 приходим к оценке f(n) = O(n^1о&^{v w}). □

Похожая теорема может быть доказана и для случая неравенства со знаком ^ вместо знака ^.

Теорема26.2 (о рекуррентном неравенстве, случай ^).Пусть вещественная функция f(n) натурального аргумента удовлетворяет неравенству

u, если n = 1,

где u, v, w, d — неотрицательные вещественные числа, причем v + w ^ ^ 1; c — положительное вещественное число. Тогда

(n(n^dlogn), если d = log₂(v + w),
f(n) = | n(n^l0&^(v+w)), если d > log₂(v + w), (26.4)

[n(n^d), если d<log₂(v + w).

Доказательство отличается от доказательства теоремы 26.1 лишь тем, что в случаях d^log₂(v + w) вместо выбора в (26.3) слагаемого, содержащего степень двойки с большим показателем, мы выбираем

§ 26. Асимптотические оценки решений рекуррентных неравенств 171

то слагаемое, которое содержит степень двойки с меньшим показа­телем. Вместо предложения 25.1 пользуемся предложением 25.2. □

Справедливость следующего предложения проверяется непосред­ственно.

Предложение 26.1.Если в условиях теорем 26.1 и 26.2 предполо­жить, что с = 0, то получим соответственно /(п) = 0(пlo&O+w)) и /(n) = n(n^l0&^(v+w)).

Пример 26.1.Вновь рассмотрим сложности рекурсивной сорти­ровки слияниями и бинарного возведения в степень. Уравнение (25.18) представим как систему двух неравенств со знаками соот­ветственно ^ и ^. Применяя к ним теоремы 26.1_и 26.2 (y + w = 2, log₂(v+w)=d = l), из первой теоремы получаем Т_ш(.п) = О(n log п), из второй — Т_ш(п) = П(п log п). В итоге имеем T_MS(n) = 6(n logn). Аналогичным образом представим в виде системы двух неравенств уравнение (25.16). Заменим в правой части п - 1 на п в случае ^ и на у в случае ^. Очевидно, что полученные неравенства являются след­ствиями исходных. С помощью теорем 26.1 и 26.2 (вновь v + w = 2, log₂(v+w) = d = l) получаем T_MS(n) = 0(n logn) и T_MS(n) = fi(nlogn). В итоге имеем T_MS(n) = 6(n logn).

Сложность рекурсивной сортировки слияниями как по числу срав­нений, так и по числу перемещений элементов массива допускает оценку 6(n log п).

Применяя теоремы 26.1 и 26.2 к (25.20), (25.21) (теперь v + w = l, log₂(v+w) = d = 0), получим T_RS(n) = О (log п) и T_RS(n) = n(logn). В итоге получаем T_RS (п) = в (log п).

Асимптотические оценки T_MS(n) = G(nlogn), T_MS(n) = G(nlogn), r_RS(n) = 6(logn) можно было бы получить и из выведенных ранее неравенств (25.19), (25.17), (25.22). Этот пример демонстрирует лишь то, что теоремы о рекуррентных неравенствах позволяют быстро по­лучать асимптотические оценки непосредственно из первоначальных рекуррентных неравенств.

Пример 26.2.Известен алгоритм построения выпуклой оболоч­ки объединения двух выпуклых многоугольников, имеющих соответ­ственно п_г и п₂ вершин, со сложностью 0{п_г + п₂) по общему числу операций, п_г + п₂ рассматривается как размер входа этого алгоритма (см. задачу 62). Стратегия «разделяй и властвуй» позволяет, исходя из этого, описать алгоритм построения выпуклой оболочки данного

172 Глава 6. Рекуррентные соотношения и сложность алгоритмов

множества n точек, сложность которого по общему числу операций при выборе n в качестве размера входа определяется соотношением

0, еслиn=1,

T(n)=

Tl+Tl +⁰^при"^°°-

От этого соотношения мы переходим к неравенству

(О, если п = 1,

'( ^ ] + т(\ ^ ] + сп, если п > 1,

где с—некоторое неизвестное нам положительное число,—мы поль­зуемся здесь тем, что если g{n) = 0(,h(n)) и fr(n) > О при п > 1, то g{n) s= ch{n) для некоторой константы с и всех п > 1.

Применяем теорему 26.1 (v + w = 2, log₂(v + w) = 1, d = 1). Это да­ет T{n) = 0{n logп). Мы имеем, таким образом, еще один алгоритм построения выпуклой оболочки п заданных точек, по общему числу операций имеющий сложность O(nlogn).

Теоремы о рекуррентных неравенствах в некоторых книгах фор­мулируется иначе (см. задачу 144). Иногда¹ в условии этой теоремы предполагается, что исследуемая сложность является неубывающей функцией от п. Перед тем как применять теорему в таком ее виде к сложности конкретного алгоритма, необходимо доказывать неубы­вание этой сложности. Неубывание не является самоочевидным фак­том для алгоритмов, построенных по стратегии «разделяй и власт­вуй». Например, для бинарного алгоритма вычисления а" это не так: T_RS(7) = 4, T_RS(8) = 3. В теоремах 26.1 и 26.2 неубывание не предпола­гается.

Еще одно замечание. В § 9 мы получали формулы и оценки для сложностей алгоритма бинарного поиска места элемента, сортиров­ки фон Неймана и т. д. путем сравнения возникающих величин с по­следовательностью 2',Z = 0,1, ...; этот прием во многом аналогичен использованию соотношений вида (25.2), (25.14), но в том лишь част­ном случае, когда одно из чисел v,w равно нулю.