Решение рекуррентного соотношения T (n) = n * T (n - 1) + n! (n> 0, T (0) = 2) - PullRequest
Новая
       2

Решение рекуррентного соотношения T (n) = n * T (n - 1) + n! (n> 0, T (0) = 2)

0 голосов
/ 02 февраля 2020

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

1 Ответ

1 голос
/ 02 февраля 2020

Просто расширить: 

T(n) = n*((n-1)*T(n-2) + (n-1)!) + n! =
       n*(n-1)*T(n-2) + n! + n!       =
       n*(n-1)*T(n-2) + 2 * n!        =
       n*(n-1)*((n-2)*T(n-3) + (n-2)!) + 2n! = 
       n*(n-1)*(n-2)*T(n-3) + 3 * n!

По индукции вы можете доказать: 

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

Как мы знаем T(0) = 2 и T(2) = 2 T(1) + 2! = 2 * (T(0) + 1) + 2 = 8: 

T(n) = 4 * n! + (n-2) * n! = (n+2) * n! = (n+1)! + n! = \Theta((n+1)!)
...