Wir können die Substitution U(n) = T(n) + 1/2 machen und dann eine Wiederholung erhalten
Das ist ein bisschen magisch, aber, wie der Schablonentyp erwähnt, kann die Magie mit der Annihilator-Methode erzeugt werden. Jetzt müssen wir nur die lineare homogene Wiederholung lösen. Das charakteristische Polynom x^2 - x - 2 Faktoren als (x+1)(x-2) , also sind die Lösungen U(n) = a(-1)^n + b2^n wobei a und b irgendwelche Konstanten sind. Äquivalent, T(n) = a(-1)^n + b2^n - 1/2 , das ist Theta(2^n) außer in speziellen Fällen.
Diese Rekursion wird nicht-homogene lineare Wiederholung genannt und wird durch Umwandlung in a gelöst homogenes:
%Vor% Wenn Sie 1 von 2 subtrahieren und die Basis ändern, erhalten Sie T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3) . Die entsprechende charakteristische Gleichung lautet:
mit Lösungen x = {-1, 1, 2} . Dies bedeutet, dass die Rekursion wie folgt aussieht:
Wo all diese Konstanten gefunden werden können, wissen wir T (0) und T (1). Für Ihre Komplexitätsanalyse ist klar, dass dies Exponential O(2^n) ist.
Tags und Links algorithm recursion recurrence asymptotic-complexity