Рис. 4.3 Дерево рекурсии для соотношения Т(п) = аТ(п/Ь) + f(n) является полным а-ичным деревом высоты logb п с nloSi,°. Сумма весов по уровням показана справа, а общая сумма даётся формулой (4.6).

Доказательство. Последовательно подставляя соотношение само в себя, получаем

Т(п)

: /(га) + аТ(п/Ь) : /(га) + af(n/b) + a2T(n/b2) : /(га) + af(n/b) + a2f(n/b2) + + а

lon-lf{n/b

lo&n-1) +а1о§ьПГ(1).

logb га

ralogba, последний член может быть записан как O(ralogba). Оставшиеся члены образуют сумму, фигурирующую в утверждении леммы.□

Поскольку a gb

Дерево рекурсии

Доказательство леммы 4.2 можно пояснить в терминах дерева рекурсии (рис. 4.3), если число а целое (хотя само доказательство этого не требует). В корне стоит число /(га), в каждом из а его детей стоит число /(га/6), в каждом из а2 внуков стоит /(га/62) и т. д. На уровне j имеется а3 вершин; вес каждой - f(n/b3). Листья находятся на расстоянии logfe га от корня, и имеют положительный вес Г(1); всего на дереве alogbn = ralogba листьев.

Равенство (4.6) получается, если сложить веса на всех уровнях: общий вес на j-m уровне есть a3 f(n/b3), а общий вес внутренней части дерева есть

logbn-l 3=0

Если рекуррентное соотношение произошло из алгоритма типа «разделяй и властвуй», эта сумма отражает стоимость разбиения задачи на подзадачи и объединения решений. Суммарный вес всех листьев есть стоимость решения всех ralogi>a задач размера 1, которая составляет O(ralogi>a).

В терминах дерева рекурсии легко объяснить, чему соответствуют три случая в формулировке основной теоремы. В первом случае основная часть веса сосредоточена в листьях, в третьем - в корне, во втором вес равномерно распределён по уровням дерева.

Теперь оценим величину суммы в формуле (4.6).

Лемма 4.3. Пусть а 1, 6 > 1 - константы, /(га) - неотрицательная функция, определённая на натуральных степенях Ь. Рассмотрим функцию д(п), определённую формулой

logbn-l

g(n)="4{n/V)(4.7)

(для n, являющихся степенями Ь). Тогда

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

2.Если /(га) = 6(га1о§ьа), то д(п) = в(га1о§ьа lg га).

3.Если af (га/6) с/(га) для некоторой константы с < 1 и для всех пЬ, то д(п) = в(/(га)).

Доказательство. 1. В первом случае достаточно доказать утверждение леммы для функции /(га) = га", где а = logfe а - е Для такой функции / равенство (4.7) может быть переписано так: (теперь а = logfe a)

д(п) = /(га) + а/(га/6) + а2/(га/62) + ... + ak~l f(n/bk-1)

= па + a(n/b)a + a2(n/b2)a + ... + ak-1(n/bk-1)a; (4.8)

правая часть представляет собой геометрическую прогрессию длины k = logfe га со знаменателем а/Ьа; этот знаменатель больше 1, так как а < logfe а и Ьа < а. Для такой прогресии сумма по порядку равна последнему члену (отличается от него не более чем на константу раз). Этот последний член есть 0(ак) = O(ralogba). Для первого случая утверждение леммы доказано.

2.Во втором случае аналогичное рассуждение даёт сумму того же вида:

дЫ) = Дга) + af(n/b) + a2f(n/b2) + ...

= па + а(п/Ъ)а + а2(п/Ь2)а + ... ,(4.9)

но теперь а = logb а и потому знаменатель геометрической прогрессии равен 1 и все её члены равны. Их число есть logfe га, и потому сумма равна

га1о§ьа1оёбга = в(га1о§ьа1ёга).

Случай 2 разобран.

3.В этом случае условие регулярности функции / гарантирует, что в нашей сумме каждый следующий член не превосходит предыдущего, умноженного на с < 1. Тем самым её можно оценить сверху убывающей геометрической прогрессией со знаменателем с, и сумма такой прогрессии не более чем в константу (равную 1/(1 - с)) раз превосходит первый член (но и не меньше его, так как все слагаемые неотрицательны). Таким образом, дЫ) = 0(/(га)) для га, являющихся степенями Ь. Доказательство леммы завершено.

□

Теперь мы можем доказать основную теорему о рекуррентных оценках для случая, когда га есть натуральная степень 6.

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

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

2.Если /(га) = 6(га1о§ьа), гао Г (га) = 6(га1о§ьа) lg га.

3.Если /(га) = £7(ralogba+e) для некоторого е > 0 и если а/(га/6) с/(га) для некоторой константы с < 1 и для достаточно больших га, то Т(п) = в(/(га)).

??????? Как убрать точку в конце слова Доказательство?

Доказательство, состоит в комбинации лемм 4.2 и 4.3. В первом случае получаем

Т(п) = в(га1о§ьа) +О(га1о§ьа) = в(га1о§ьа).

Во втором случае имеем

ТЫ) = в(га1о§ьа) +в(га1о§ьа1ёга) = в(га1о§ьа lg га).