Т(га/6) на T([ra/6J) или Т([га/6]). Оба варианта, как мы увидим в следующем разделе, приводят к одному и тому же ответу, и для простоты мы будем опускать округление в наших формулах.

Основная теорема о рекуррентных оценках

Теорема 4.1. Пусть а 1 и 6 > 1 - константы, /(га) - функция, Г (га) определено при неотрицательных га формулой

Г(га) = аТ{п/Ъ) + /(га),

где под п/Ь понимается либо [га/6], либо [га/6]. Тогда:

1.Если /(га) = O(ralogba e) для некоторого е > 0, то Т(п) = 0(га1о§ьа).

2.Если /(га) = 0(ralogba), гао Г(га) = 0(ralogba lgra).

3.Если /(га) = S7(ralogba+e) о"лл некоторого е > 0 и если а/(га/6) с/(га) о"лл некоторой константы с < 1 и достаточно больших га, то Г(га) = 0(/(га)).

В чём суть этой теоремы? В каждом из трёх случаев мы сравниваем /(га) с ralogba; если одна из этих функций растёт быстрее другой, то она и определяет порядок роста Т(п) (случаи 1 и 3). Если обе функции одного порядка (случай 2), то появляется дополнительный логарифмический множитель и ответом служит формула 0(ralogbalgra) = 0(/(ra) lgra).

Отметим важные технические детали. В первом случае недостаточно, чтобы /(га) была просто меньше, чем ralogba: нам нужен «зазор» размера гае для некоторого е > 0. Точно так же в третьем случае /(га) должна быть больше ralogba с запасом, и к тому же удовлетворять условию «регулярности» a/(ra/6) с/(га); проверка последнего условия, как правило, не составляет труда.

Заметим, что три указанных случая не исчерпывают всех возможностей: может оказаться, например, что функция /(га) меньше, чем ralogba, но зазор недостаточно велик для того, чтобы воспользоваться первым утверждением теоремы. Аналогичная «щель» есть и между случаями 2 и 3. Наконец, функция может не обладать свойством регулярности.

Применения основной теоремы

Рассмотрим несколько примеров, где применение теоремы позволяет сразу же выписать ответ. Для начала рассмотрим соотношение

Г(га) = 9Г(га/3) + га.

В этом случае а = 9, 6 = 3, /(га) = га, а ralogba = ralogs9 = 0(ra2).

Поскольку /(га) = О(га1о&з9 е) для е = 1, мы применяем первое утверждение теоремы и заключаем, что Т(п) = 0(га2). Теперь рассмотрим соотношение

Т(п) = Т(2га/3) + 1.

Здесь а = 1, Ъ = 3/2, /(га) = 1 и ralogba = ralog3/21 = га0 = 1. Подходит случай 2, поскольку /(га) = O(ralogba) = ©(1), и мы получаем, что Г(га) = ©(lgra). Для соотношения

Г(га) = ЗГ(га/4) + га lgra

мы имеем а = 3, Ь = 4, /(га) = га lgra; при этом ralogba = ralog43 (9(га0.793) Зазор (с£й 0,2) есть, остаётся проверить условие регулярности. Для достаточно большого га имеем af(n/b) = 3(га/4) lg(ra/4) (3/4)ralgra = с/(га) для с = 3/4. Тем самым по третьему утверждению теоремы Т(п) = ©(ralgra).

Вот пример, когда теорему применить не удаётся: пусть Т(п) = 2Г(га/2) + га lgra. Здесь а = 2, Ь = 2, /(га) = ralgra, ralogba = га. Видно, что /(га) = ralgra асимптотически больше, чем ralogba, но зазор недостаточен: отношение /(ra)/ralogba = (ralgra)/ra = lgra не оценивается снизу величиной гае ни для какого е > 0. Это соотношение попадает в промежуток между случаями 2 и 3; для него можно получить ответ по формуле из упр. 4.4-2.

Упражнения

4.3-1 Используя основную теорему, найдите асимптотически точные оценки для соотношения

а.Г(га) = AT (п/2) + га;

б.Т(п) = 4Г(га/2) + га2;

в.Т(п) = 4Г(га/2) + га3.

4.3-2 Время работы алгоритма А описывается соотношением Т(п) = IT (п/2) +га2, а время работы алгоритма А - соотношением Г(га) = аТ(п/А) +га2. При каком наибольшем целом значении а алгоритм А асимптотически быстрее, чем А1

4.3-3 Используя основную теорему, покажите, что соотношение Т(п) = Т(п/2) +0(1) (для двоичного поиска, см. упр. 1.3-5) влечёт Т(п) = ©(lgra).

4.3-4 Покажите, что условия регулярности (случай 3) не вытекает из других условий: приведите пример функции /, для которой существует требуемая константа е, но условие регулярности не выполнено.

★ 4.4 Доказательство Теоремы 4.1

Мы приведём доказательство теоремы 4.1 для дотошных читателей; в дальнейшем оно не понадобится, так что при первом чтении его вполне можно пропустить.

Доказательство состоит из двух частей. Сначала мы рассматриваем только те га, которые являются степенями числа Ь; все основные идеи видны уже для этого случая. Затем полученный результат распространяется на все натуральные числа, при этом мы аккуратно следим за округлениями и т. п.

В этом разделе мы позволим себе не совсем корректно обращаться с асимптотической записью: будем использовать её для функций, определённых только на степенях числа Ь, хотя определение требует, чтобы оценки доказывались для всех достаточно больших натуральных чисел.

Из контекста будет понятно, что имеется в виду, но нужно быть внимательным, чтобы не запутаться: если о функции Т(п) ничего не известно, то оценка Т(п) = О (га) для га, являющихся степенями двойки, ничего не гарантирует для произвольных га. (Возможно, что Т(п) = га при га = 1, 2, 4, 8,... и Т(п) = га2 при остальных га.)

4.4.1. Случай натуральных степеней

Пусть Т(п) определено для чисел, являющихся (натуральными) степенями числа Ь > 1 (не обязательно целого) и удовлетворяет соотношению (4.5), т.е.

Мы получим оценку для Г так: перейдём от этого соотношения к суммированию (лемма 4.2), затем оценим полученную сумму (лемма 4.3) и подведём итоги (лемма 4.4).

Лемма 4.2. Пусть а 1, Ь > 1 - константы, и пусть /(га) - неотрицательная функция, определённая на степенях Ь. Пусть Г (га) - функция, определённая на степенях Ь соотношением Т(п) = аТ(п/Ь) + /(га) при га > 1, причём Г(1) > 0. Тогда

Т(п) = аТ(п/Ь) + /(га).

(4.6)