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

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

Рассмотренный метод оценивания решений рекуррентных нера­венств (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).

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

t{k) =

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

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

(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) слагаемого, содержащего степень двойки с большим показателем, мы выбираем