Ich bin nicht mit Rezidiv-Lösungsmethoden außerhalb des Master-Theorems, Rekursionsbäume und der Substitutionsmethode vertraut. Ich vermute, dass für eine Big-O Bindung die folgende Wiederholung der Lösung nicht einer dieser Methoden nicht nutzen:Wie löst man die folgende Wiederholung?
T(n) = T(n-1) + 2T(n-2) + 1
Wir U(n) = T(n) + 1/2 die Substitution machen und dann eine Wiederholung bekommen
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),
, die a wenig magie, aber, wie der Templatetyp 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 wie (x+1)(x-2), so dass die Lösungen U(n) = a(-1)^n + b2^n sind, 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 besonderen Fällen.
Diese Rekursion non-homogeneous linear recurrence. genannt wird, und es wird gelöst, indem es zu einem homogenen einer Umwandlung:
T(n) = T(n-1) + 2T(n-2) + 1
T(n+1) = T(n) + 2T(n-1) + 1
1 von 2 Subtrahierend und die Basis zu ändern, erhalten Sie T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3). Die entsprechende charakteristische Gleichung ist:
x^3 - 2x^2 - x + 2 = 0
die x = {-1, 1, 2} Lösungen. Dies bedeutet, dass die Rekursion wie folgt aussieht:
c1 * (-1)^n + c2 * 2^n + c3 * 1^n = c1 * 2^n + c2 (-1)^n + c3
Wo alle diese Konstanten gefunden werden können, T (0) und T (1) zu kennen. Für Ihre Komplexitätsanalyse ist klar, dass dies exponentiell ist O(2^n).
Was ist der Basisfall für 'T (n)'? –
Dies ist ein großartiger Ort, um die Annihilator-Methode zu verwenden ... die ich eigentlich nicht weiß. :-) – templatetypedef
Ein Base Case ist nicht vorgesehen. Ich schätze, dass es nicht nötig ist, ein großes O-Band zu erreichen? – velen