Шаг 56.
Рекурсия на Python. Анализ времени выполнения ... . Однородные рекуррентные соотношения: характеристический полином с кратными корнями

    На этом шаге мы рассмотрим, где и как используется этот полином.

    В предыдущем шаге показано, что если кратность корней ri, соответствующих члену (х - ri) в разложении на множители характеристического полинома, равна 1, то формула для T(n) будет содержать член Cirin. Если же кратность m корня r больше 1, то, исходя из (x - r)m, T(n) будет содержать m членов вида "константа * полином * rn", при этом полиномы должны иметь различные степени n в диапазоне от 0 до m - 1. Например, член (х - 2)4 в разложении на множители характеристического полинома привёл бы к четырём следующим слагаемым в формуле для T(n): 

    C12n + C2n2n + C3n22n + C4n32n
для некоторых констант C. Поэтому T(n) можно записать в общем виде как 
    T(n) = C1P1(n)r1n + ... + CkPk(n)rkn,     (3.42)
где P(n) - полиномы вида nc для некоторого с.

    В качестве примера рассмотрим следующее рекуррентное соотношение: 

    T(n) = 5T(n - 1) - 9T(n - 2) + 7T(n - 3) - 2T(n - 4),
для которого T(0) = 0, T(1) = 2, T(2) = 11 и T(3) = 28. Его можно записать как 
    T(n) - 5T(n - 1) + 9T(n - 2) - 7T(n - 3) + 2T(n - 4) = 0,
что приводит к характеристическому полиному: 
    x4 - 5x3 + 9x2 - 7x + 2.

    Его можно разложить на множители (например, с помощью правила Руффини) следующим образом: 

    (x - 1)3(x - 2),
из чего следует, что формула рекуррентного соотношения будет иметь вид: 
    T(n) = C1 * 1 * 1n + C2 * n * 1n + C3 * n2 * 1n + C4 * 1 * 2n = 
         = C1 + C2n + C3n2 + C42n,
в которой есть слагаемые, связанные с корнем r = 1. Константы определяются из решения следующей системы линейных уравнений: 
    C1 + C4 = 0 = T(0)
    C1 + C2 + C3 + 2C4 = 2 = T(1)
    C1 + 2C2 + 4C3 + 4C4 = 11 = T(2)
    C1 + 3C2 + 9C3 + 8C4 = 28 = T(3)

    Её решение: 

    C1 = -1, 
    C2 = -2, 
    C3 = 3 и 
    C4 = 1.
(В примере 3.2 приводится код для решения системы линейных уравнений вида Ax = b с помощью пакета NumPy.) В итоге получаем: 
    T(n) = -1 - 2n + 3n2 + 2n ∈ Θ(2n)
с экспоненциальным порядком роста.
Пример 3.1. Решение системы линейных уравнений Ax = b
1
2
3
4
5
6		 
import numpy as np

A = np.array([[1, 0, 0, 1], [1, 1, 1, 2],
              [1, 2, 4, 4], [1, 3, 9, 8]])     
b = np.array([0, 2, 11, 28])
x = np.linalg.solve(A, b)
Архив с файлом можно взять здесь.

    На следующем шаге мы рассмотрим неоднородные рекуррентные соотношения.




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