Non ho familiarità con le tecniche di risoluzione delle recidive al di fuori del teorema principale, degli alberi di ricorsione e del metodo di sostituzione. Sto indovinando che la soluzione del seguente ricorrenza per una grande-O bound non utilizza uno di questi metodi:Come risolvere la seguente recidiva?
T(n) = T(n-1) + 2T(n-2) + 1
Possiamo fare la sostituzione U(n) = T(n) + 1/2 e quindi ottenere una ricorrenza
U(n) = T(n) + 1/2
= T(n-1) + 2T(n-2) + 1 + 1/2
= T(n-1) + 1/2 + 2(T(n-2) + 1/2)
= U(n-1) + 2U(n-2),
che è un poca magia ma, come menziona templatetypedef, la magia può essere creata con il metodo annientatore. Ora dobbiamo solo risolvere la recidiva omogenea lineare. I fattori polinomiali caratteristici x^2 - x - 2 sono (x+1)(x-2), quindi le soluzioni sono U(n) = a(-1)^n + b2^n dove a e sono tutte le costanti. Equivalentemente, T(n) = a(-1)^n + b2^n - 1/2, che è Theta(2^n) tranne in casi speciali.
Questa ricorsione è chiamato non-homogeneous linear recurrence. ed è risolto convertendolo in un omogeneo uno:
T(n) = T(n-1) + 2T(n-2) + 1
T(n+1) = T(n) + 2T(n-1) + 1
Sottraendo 1 da 2 e cambiando la base, si ottiene T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3). La corrispondente equazione caratteristica è:
x^3 - 2x^2 - x + 2 = 0
che ha soluzioni x = {-1, 1, 2}. Ciò significa che la ricorsione assomiglia:
c1 * (-1)^n + c2 * 2^n + c3 * 1^n = c1 * 2^n + c2 (-1)^n + c3
Dove tutte queste costanti possono essere trovati sul fatto T (0) e T (1). Per la tua analisi di complessità è chiaro che questo è esponenziale O(2^n).
Qual è il caso base per 'T (n)'? –
Questo è un ottimo punto per usare il metodo annihilator ... che in realtà non so come fare. :-) – templatetypedef
Un caso base non è fornito. Suppongo che non sia necessario per raggiungere un limite O-grande? – velen