Mi è stato chiesto di capire l'analisi della complessità temporale per la seguente relazione di ricorrenza
T(n) = 4*T(n-1) + c .
Fondamentalmente, ho fatto una sostituzione .. T(n-1) = 4 * T(n-2) + c e così via ..
T(n) = 4^k T(1) + c(1 + 4 + 4^2..4^(k-1))
L'ho risolto come O (4 ^ k) Vorrei sapere se questo è giusto o sbagliato?
O(4^n) sembra essere corretto in quanto c(1 + 4 + 4^2 + .. + 4^(n-1)) dà c(4^n - 1) / 3 riducendolo quindi a O(4^n) e la prima parte è già O(4^n) .
Sì, hai ragione.
La versione omogenea della tua relazione di ricorrenza è semplicemente T(n) = 5*T(n-1) - 4*T(n-2) (Puoi ottenere questo esprimendo c nella formula per T(n) e nella formula per T(n-1) e quindi equiparandoli).
Il polinomio caratteristico della relazione è quindi x^2 - 5x + 4 = 0 . Risolvendoti ottieni le radici 1 e 4 . Quindi qualsiasi soluzione della relazione di ricorrenza ha forma a * 4^n + b * 1^n , che si semplifica in a * 4^n + b . I valori di a e b dipendono dalle condizioni iniziali (il valore di c e T(0) ). Ad esempio, per c = 1 e T(1) = 1 , la soluzione è 1/3 * 4^n - 1/3 - puoi verificarlo da solo!
La strategia generale di risoluzione di questi semplici tipi di relazioni di ricorrenza è descritta nella Wiki .
Leggi altre domande sui tag recursion big-o algorithm-analysis