На этом шаге мы рассмотрим примеры их использования.

Рассмотрим функцию (3.18). Её рекурсивное условие

    T(n) = T(n - 1) + b      (3.21)

можно неоднократно применять (к аргументам с меньшими значениями) для "расширения" слагаемого T в правой части. Например, T(n - 1) = T(n - 2) + b - это результат подстановки (n - 1) вместо n в (3.21). Таким образом, мы приходим к соотношению

    T(n) = [T(n - 2) + b] + b = T(n - 2) + 2b,

где выражение в квадратных скобках - это расширение T(n - 1). Этот приём можно применить снова, расширив T(n - 2) до T(n - 3) + b. Таким образом, на третьем шаге мы получим:

    T(n) = [T(n - 3) + b] + 2b = T(n - 3) + 3b.

После нескольких таких расширений у нас должна появиться возможность выявить закономерность и вывести общую формулу, соответствующую некоторому шагу i. Общая формула для этой функции:

    T(n) = T(n - i) + i * b.	(3.22)

В конце концов, при некотором значении i процесс достигнет начального условия. Для функции (3.18) оно определяется как T(1). Следовательно, слагаемое T(n - i) достигнет начального условия при n - i = 1 или при i = n - 1. Подстановка этого значения в (3.22) позволяет нам избавиться от переменной i в этой формуле и получить полностью нерекурсивное определение T(n):

    T(n) = T(1) + (n - 1) b = a + (n - 1) b = b * n - b + a ∈ Θ(n).

Таким образом, код из примера 1.1 выполняется за линейное от n время.

Ниже приведена справка о методе расширения, который мы теперь будем применять к другим рекуррентным соотношениям.

Выписать рекурсивное условие из рекуррентного соотношения.
Несколько раз расширить рекурсивный член в правой части, пока не удастся выявить общую формулу для произвольного шага i.
Определить значение i, при котором выполняется начальное условие.
Подставить полученное значение i в общую формулу.

Рассмотрим процесс расширения функции (3.20):

    T(n) = T(n/2) + b                         {шаг 1}
         = T(n/4) + b + b = T(n/4) + 2b       {шаг 2}
         = T(n/8) + b + 2b = T(n/8) + 3b      {шаг 3}
         = T(n/16) + b + 3b = T(n/16) + 4b    {шаг 4} ...

Её общая формула для рекуррентного соотношения на шаге i:

    T(n) = T(n/2ⁱ) + i * b.    (3.23)

Начальное условие T(1) выполняется при n/2ⁱ = 1, то есть при n = 2ⁱ или при i = log2 n. Подставив полученное значение i в (3.23), получаем:

    T(n) = T(1) + b log₂ n = a + b log₂ n ∈ Θ(log n).

Поскольку её порядок роста - логарифмический, код примера 1.1 с линейным порядком роста асимптотически медленнее кода примера 2.9. Интуитивно это понятно: первый уменьшает размер задачи на 1, тогда как второй делит размер исходной задачи пополам и за счёт этого приходит к начальному условию за меньшее количество рекурсивных вызовов функции.

На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг