На этом шаге мы разберем, как поступать в случае неоднородных рекуррентных соотношений.

    Неоднородные рекуррентные соотношения содержат в своей правой части нерекурсивные члены. Для таких рекуррентных соотношений тоже можно вывести общую формулу, если нерекурсивные члены представляют собой произведение полинома на экспоненту (см. (3.33)). Процедура решения - та же, но каждому члену P^d_i(n)b_iⁿ в характеристическом полиноме соответствует слагаемое (x - b_i)^d_i+1, где d_i - степень полинома P_i(n).

    Рассмотрим следующее рекуррентное соотношение:

    T(n) = 2T(n - 1) - T(n - 2) + 3n + n3n + 3 + n + n2.

    Как и в предыдущих примерах, первый шаг - это перенос T-разностей в левую часть рекуррентного соотношения:

    T(n) - 2T(n - 1) + T(n - 2) = 3n + n3n + 3 + n + n2.

    На следующем шаге нужно представить каждый член правой части в виде произведения полинома на экспоненту. Если этот член состоит только из экспоненты, то естественно умножить его на полином n⁰ = 1. Если же он представляет собой только полином, то он умножается на экспоненту 1ⁿ. Таким образом, рекуррентное соотношение можно записать в виде:

    T(n) - 2T(n - 1) + T(n - 2) = 1 * 3n + n * 3n + 3 * 1n + n * 1n + n2 * 1n.

    Если какая-то экспонента встречается в правой части несколько раз, она должна умножаться только на один полином. Следовательно, экспоненты правой части нужно сгруппировать:

    T(n) - 2T(n - 1) + T(n - 2) = (1 + n) * 3n + (3 + n + n2) * 1n. 

    На следующем шаге определяется характеристический полином. В левой части мы имеем (x² - 2x + 1) = (x - 1)². В правой части члену (1 + n) * 3ⁿ соответствует (x - 3)², где 3 - основание экспоненты, а 2 - степень полинома (1) плюс 1. Аналогично члену (3 + n + n²) * 1ⁿ соответствует (x - 1)³. Таким образом, характеристический полином имеет вид:

    (x - 1)2(x - 3)2(x - 1)3 = (x - 1)5(x - 3)2, 

    T(n) = C1 + C2n + C3n2 + С4n3 + C5n4 + С63n + С7n3n.

    Проиллюстрируем данный подход следующим примером неоднородного рекуррентного соотношения:

            1,                  если n = 0
    T(n) = 
            2T(n - 1) + n + 2n, если n > 0.

    Сначала приводим рекурсивное условие к каноническому виду:

    T(n) - 2T(n - 1) = n * 1n + 1 * 2n.

    Соответствующий ему разложенный на множители характеристический полином:

 (x - 2) {из T(n) - 2T(n - 1)} * (x - 1)2 {из n * 1n} * (x - 2) {из 1 * 2n} = (x - 1)2(x - 2)2, 

    T(n) = С1 + С2n + С32n + С4n2n.

    Поскольку у нас есть четыре неизвестные константы, нам нужны значения T для четырёх различных n. Это значит, что к уже имеющемуся значению из начального условия T(0) = 1 нужно добавить из рекурсивного условия T(n) = 2T(n - 1) + n + 2ⁿ ещё три - T(1), T(2) и T(3), а именно: T(1) = 5, T(2) = 16 и T(3) = 43. Теперь на основании этих данных можно записать следующую систему линейных уравнений:

    C1 + С3 = 1 = T(0)
    С1 + С2 + 2С3 + 2С4 = 5 = T(1)
    С1 + 2С2 + 4С3 + 8С4 = 16 = T(2)
    С1 + 3С2 + 8С3 + 24С4 = 43 = T(3).

    Её решение:

    С1 = -2, 
    С2 = -1, 
    С3 = 3, 
    С4 = 1   . 

    T(n) = -2 - n + 3 * 2n + n2n ∈ Θ(n2n).

    На следующем шаге мы рассмотрим дробные аргументы рекурсивной функции.

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