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

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

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

(

и, если п = 1,

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

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

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

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

t{k) =

u, если k =0,

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

имеет вид

t (fc)= c o(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 Гю_§2 n 1(2^2 n У.

Это дает 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) натурального аргумента удовлетворяет неравенству

f (l§J) +wf\i])+cn^d' еслиn>1>

(

u, если n = 1,

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

(n(n^d log n), если 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 log n). Аналогичным образом представим в виде системы двух неравенств уравнение (25.16). Заменим в правой части п - 1 на п в случае ^ и на у в случае ^. Очевидно, что полученные неравенства являются след­ствиями исходных. С помощью теорем 26.1 и 26.2 (вновь v + w = 2, log₂(v + w) = d = l) получаем T _MS(n) = 0(n log n) и T _MS(n) = fi(n log n). В итоге имеем T _MS(n) = 6(n log n).

Сложность рекурсивной сортировки слияниями как по числу срав­нений, так и по числу перемещений элементов массива допускает оценку 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(log n). В итоге получаем T_RS (п) = в (log п).

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

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

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

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

0, если n =1,

T (n)=

T l +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 (n log n).

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

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

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