Как решить это повторение: T (n) = 2T (n / 3) + n ^ 2?

Question

Метод замещения и метод дерева рекурсии для:

• T (n) = 2/7 Если n = 1

• T (n ) = 2T (n / 3) + n ^ 2 В противном случае

Как решить такую ​​систему уравнений?

Answer 1

Уравнение может быть ясно решено только тогда, когда n является степенью 3. Подстановка n новой переменной k^3 дает более простое уравнение, которое может быть решено с помощью sympy , python символы c математическая библиотека:

from sympy import Function, rsolve, S, symbols, Eq

k, n = symbols("k n", integer=True, positive=True)

f = Function('f')
g = Function('g')

# T(n) = 2T(n/3)+n^2    T(1) = 2/7

T = Eq(f(n), 2 * f(n / 3) + n * n)
Tk = T.subs({n: 3 ** k, f(n): g(k), f(n / 3): g(k - 1)})

s = rsolve(Tk, g(k), {g(0): 2 / S(7)})
print("solution for k:", s.cancel())

for k in range(0, 11):
    print(f"k={k}, n={3 ** k}, T(n)={-2 ** k + 3 ** (2 * k + 2) / S(7)}")

В результате получается следующая формула для k: -2 ^k + 3 ^{2 * k + 2} / 7

Значения для k = 0..10:

k=0, n=1, T(n)=2/7
k=1, n=3, T(n)=67/7
k=2, n=9, T(n)=701/7
k=3, n=27, T(n)=6505/7
k=4, n=81, T(n)=58937/7
k=5, n=243, T(n)=531217/7
k=6, n=729, T(n)=4782521/7
k=7, n=2187, T(n)=43045825/7
k=8, n=6561, T(n)=387418697/7
k=9, n=19683, T(n)=3486780817/7
k=10, n=59049, T(n)=31381052441/7