Может ли кто-нибудь помочь мне решить эту проблему, используя метод подстановки?

Question

Может ли кто-нибудь помочь мне решить эту проблему? T (n) = 8T (n / 2) + n ^ 2 - это T (n) = O (n ^ 3) с использованием метода подстановки. С учетом T (1) = 1

Answer 1

Просто попробуйте расширить отношение и продолжить по индукции:

T(n) = 8 T(n/2) + n^2 =
       8(8T(n/4) + (n/2)^2) + n^2 = 8^2 T(n/2^2) + 8 (n/2)^2 + n^2

Поскольку каждый раз n делится на 2 каждый раз, если n = 2^k, длина серии k = log(n):

T(n) = n^2 + 8 (n/2)^2 + 8^2 (n/2^2)^2 + ... + 8^log(n) T(1)
     = sum_{i=0}^{log(n)} 8^i (n/2^i)^2

Перепишите отношение следующим образом: 2^2i = 4^i:

T(n) = sum_{i=0}^{log(n)} 8^i/4^i n^2 = n^2 * sum_{i=0}^{log(n)} 2^i
     = n^2 (2^(log(n)+1) - 1) = \Theta(n^3)

Обратите внимание, что 2^log(n) = n.

Answer 2

Один из способов приблизиться к этому рекуррентному отношению - это rsolve из sympy , Python символов c математическая библиотека:

from sympy import Function, rsolve, log
from sympy.abc import k, n

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

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

s = rsolve(Tk, g(k), {g(0): 1})
print("solution for k:", s.cancel())
print("solution for n:", s.subs({k: log(n, 2)}).simplify().cancel())

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

Это выводит решение (17*n^3 - 3)/7 - n^2. Обратите внимание, что функция определена только для n степени 2. Первые значения для n=1,2,4,8,...: 1, 15, 139, 1179, 9691, 78555, 632539, 5076699, 40679131, 325695195, 2606610139