В третьем случае

т(п) = в(п1о§ь«) + е(/(п)) = е(/(п)).

Заметим, что в последнем случае условие «/(га) = £7(ralogba+e) для некоторого е > 0» можно было бы опустить, так как оно вытекает из условия регулярности (см. упр. 4.4-3).□

Лемма 4.4 доказана. 4.4.2. Целые приближения сверху и снизу

Нам осталось разобраться подробно с произвольными га, не являющимися степенями числа 6. В этом случае га/6 подлежит округлению и соотношение имеет вид

Г(га) = аТ(\п/Ъ]) +/(га)(4.10)

или

Т(п) = aT([n/b\) + f(n).(4.11)

Надо убедиться, что оценка остаётся в силе и для этого случая.

Посмотрим, какие изменения надо внести в наши рассуждения. Вместо последовательности га, га/6, га/62,... теперь надо рассматривать последовательность щ, определённую так:

{га,если г = 0,.

г ik\(4-12)

ra8 i/61, если г > 0.

(мы рассматриваем случай округления с избытком). Эта последовательность - убывающая, но не обязательно стремится к единице. Однако мы можем утверждать, что после logfe га итераций получится число, ограниченное не зависящей от га (хотя зависящей от 6) константой.

В самом деле, из неравенства [~ж] ж + 1 следует, что

п0 га, га

Щ - + 1, га 1

га 1 1

Поскольку 1 + 1/6 + 1/62 + ... 1/(6 - 1), для г = logfe raj мы получаем щ га/6г + 6/(6 - 1) 6 + 6/(6 - 1) = 0(1).

Итерируя соотношение (4.10), мы получаем

Т(га) = f(n0) + аТ(щ)

= f(n0) + а/(щ) + а2Т(п2)

/(«о) + а/Ю + a2f(n2) + ...+ + aLbSbnJ-i/(raLiogbnj i) + aLioSbnjr(raLiogbnj)

= в(пь§ьа)+ a3f(ni)-(4-13)

j=0

Это выражение очень похоже на (4.6), только здесь га не обязано быть степенью числа Ь.

[Строго говоря, сказанное требует некоторых уточнений. Дело в том, что величина Т(п\\0%Ъп\) может оказаться равной нулю. Но мы знаем, что /(га) асимптотически положительна, т.е. положительна для всех га, начиная с некоторого гао- Поэтому в развёртывании суммы нужно остановиться, немного не дойдя до этого гао- Мы опускаем подробности.]

Теперь надо разобраться с соотношениями между слагаемыми в сумме

Llo§b "J-1

9(п)= £ аЧ{щ).(4.14)

з=о

Раньше мы сравнивали эту сумму с геометрической прогрессией, в которой знаменатель был больше единицы (первый случай), равен единице (второй случай) или меньше единицы (третий случай). Третий случай не вызывает дополнительных проблем, так как в условии регулярности также предусматривается округление (причём в ту же сторону, что и в рекуррентном соотношении). Во втором случае мы должны оценить, насколько велики изменения вследствие замены п/Ьг на гц. Как мы видели, разница не превосходит Ь/(Ь - 1), но надо ещё от абсолютной ошибки перейти к относительной. Нам надо проверить, что /(raj) = O(ralogba/aJ) = 0((ra/6-?)logba), тогда проходит доказательство леммы 4.3 (случай 2). Заметим, что Ь3/га 1 при j [logferaJ. Из оценки /(га) = O(ralogi>a) вытекает, что для подходящего с и

Задачи к главе 4

71

достаточно больших rij

(га Ь \logb а

/rabgbaX /b Xbgba

/„logba\

Последний переход использует то, что с(1 + Ь/(Ь - l))logba - константа. Итак, случай 2 разобран.

Рассуждение для случая 1 почти такое же. Там нужно доказать оценку f(iij) = O(ralogba e); а это делается примерно так же, как и в случае 2, хотя преобразования будут несколько сложнее.

Итак, мы рассмотрели случай произвольного га для округления с избытком. Аналогично можно рассмотреть случай округления с недостатком, при этом нужно будет доказывать, что rij не может быть сильно меньше п/Ь3.

Упражнения

4.4-1* Укажите простую явную формулу для гц из (4.12), если Ь - положительное целое число.

4.4-2* Покажите, что если /(га) = @(ralogba lgk га), где k 0, то соотношение (4.5) влечёт Т(п) = O(ralogba lgfc+1 га). Для простоты рассмотрите лишь случай целых степеней Ь.

4.4-3* Покажите, что в случае 3 основной теоремы одно из условий лишнее: условие регулярности (af(n/b) с/(га) для некоторого с < 1) гарантирует, что существует е > 0, для которого /(га) = fi(ralogba+e).

Задачи

4-1 Примеры рекуррентных соотношений

Дайте как можно более точные асимптотические верхние и нижние оценки для следующих соотношений (считаем, что Т(п) - константа при га 2):

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

б.Г(га) = Г(9га/10) + га.