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

Предыдущее рекуррентное соотношение (3.45) можно решить, применив две последовательные замены переменной (и функции). Во-первых, замена n = 2^k приводит к

                _{__}
    T(2^k) = 2T(√n^k) + log₂ 2^k = T(2^k/2) + k.

Заменив T(2^k) на t(k), получаем следующее рекуррентное соотношение:

    t(k) = 2t(k/2) + k,

которое всё ещё нельзя решить общим методом, так как оно не является разностным уравнением. Но зато можно произвести ещё одну замену переменной k = 2^m, чтобы привести его к нужному виду:

    t(2^m) = 2t(2^m-1) + 2^m,

что после замены функции t(2^m) = u(m) сводится к разностному уравнению

    u(m) = 2u(m - 1) + 2^m.

Его характеристический полином (х - 2)², а это значит, что рекуррентное соотношение будет иметь вид:

    u(m) = C₁2^m + C₂m2^m.

Отмена последней замены переменной приводит к

    t(k) = C₁k + C₂(log₂(k))k

и в итоге к

    T(n) = C₁ log₂ n + C₂(log₂(log₂ n))log₂ n,

что равносильно (3.46). Поэтому решением является (3.47).

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

         1/3,      если = 1
T (n) =	
         nT(n/2)², если n > 1,

где n - степень двух. Сначала можно применить замену переменной n = 2k, что приводит к

    T(2^k) = 2^kT(2^k/2)² = 2^kT(2^k-1)².

После замены функции T(2^k) = t(k) получаем

    t(k) = 2^kt(k - 1)2,

что всё ещё невозможно решить общим методом. Но после логарифмирования обеих частей равенства

    log₂ t(k) = log₂ 2^kt(k - 1)² = k + 2log₂ t(k - 1)

можно произвести более сложную замену функции log₂ t(k) = u(k), которая даст рекуррентное соотношение

    u(k) = k + 2u(k - 1),

которое уже можно решить общим методом. Его характеристический полином

    (x - 2)(x - 1)²,

который подразумевает, что u(k) имеет следующий вид:

    u(k) = C₁2^k + C₂ + C₃k.

Отменив замены, получим сначала

    t(k) = 2^{C₁2^k + C₂ + C₃k},

а затем

    T(n) = 2^{C₁n + C₂ + C₃log₂ n}.

Последний шаг, как обычно, состоит из определения констант. Используя начальное условие T(1) = 1/3, получаем T(2) = 2[T(1)]² = 2/9 и T(4) = 4[T(2)]² = 4(2/9)² = 16/81. Воспользуемся этими значениями для составления следующей системы (нелинейных) уравнений:

    2^С₁+С₂ = 1/3 = T(1)
    2^{2C_l+C₂+С₃} = 2/9 = T(2)	,
    2^{4C_l+C₂+2С₃} = 16/81 = T(4)

которую (после логарифмирования по основанию 2 обеих частей уравнений) можно привести к системе линейных уравнений:

    C₁ + C₂ = -log₂3
    2C₁ + C₂ + C₃ = 1 - log₂9 = 1 - 2log₂3	.
    4C₁ + C₂ + 2C₃ = 4 - log₂81 = 4 - 4log₂3.

Её решение:

    C₁ = 2 - log₂ 3 = log₂(4/3), 
    C₂ = -2, 
    C₃ = -1.

Таким образом, T(n) можно выразить следующей формулой:

    T(n) = 2^{(log₂(4/3))n - 2 - log₂n} = 2log₂(4/3)n * 2^-2 * 2^log₂(1/n) = (4/3)ⁿ(1/4)n ∈ Θ((4/3)ⁿn).

Со следующего шага мы начнем рассматривать основные алгоритмы линейной рекурсии.

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