Rekurrenzgleichung(en) Lösen

Question

aus meinem Interesse heraus, wollte ich gerne lernen, wie man Rekurrenzgleichungen lösen kann. Ich habe dazu im wesentlichen zwei Aufgaben gefunden:

T(n) = 2T(n/3) + n^2

T(n) = 2T(n-1)+1

Kann mir vielleicht jemand anhand dieser Aufgaben verraten und erklären, wie man diese Gleichungen lösen soll/kann.

Ich danke für kommende Antworten ! 

Answer 1

Durch die Rekursion alleine sind die Werte nicht festgelegt.
Du brauchst immer noch einen Anfangswert.
Nehmen wir z.B.      T(n) = 2T(n-1)+1  und Anfang  T(1)=0

Dann kann man sich immer erst mal ein paar Werte ausrechnen, etwa

T(2) =  2*T(1) + 1 =  1
T(3) =  2*T(2) + 1 =  3
T(4) =  2*T(3) + 1 =  7
T(5) =  2*T(4) + 1 =  15

und wenn man dann die Ergebnisse betrachtet sieht man manchmal
auch eine Möglichkeit, das durch eine Formel darzustellen, hier wäre das etwa
T(n)= 2^n-1 - 1   denn für n=5 ist das eben 2^4 - 1 = 16-1 = 15
                            und für n=4 ist das eben 2^3 - 1 = 8-1 =7 
ordnungsgemäß beweisen kann man das mit vollständiger Induktion.

Comments

Danke für deine Antwort,

Aber kann man das nicht Mittels Master Theorem lösen ?

Answer 2

Das Master-Theorem gilt nur für Gleichungen mit folgendem Aufbau:

T(n) = a * T ( n / b ) + n^c, für n > 1

T(n) = d, für n = 1

Es gibt insgesamt 3 Fälle. Man kann anhand des Falles direkt eine Komplexitätsabschätzung machen.

1. a < b^c ---> T(n) = Teta (n^c)

2. a = b^c ---> T(n)n = Teta (n^c * log n)

3. a > b^c ---> T(n) = Teta (n^{log (b) a})

Nun musst du nur hingehen und gucken was bei dir a,b und c ist.

- T(n) = 2T(n/3) + n²

^{a = 2, b = 3, c = 2}

^{b^c = 3^2 = 9 > 2 = a}

^{Es handelt sich um den 1. Fall. Also ist das Ergebnis: Teta (n^2)}

- T(n) = 2T(n-1)+1

Wie man sieht, gibt es hier kein b. Von daher kann man diese Gleichung nicht mit dem Master-Theorem lösen!

Es handelt sich hierbei um eine inhomogene lineare Rekurrenzgleichung und ist mit anderen Methoden zu bearbeiten.

P.S. Wie mein Vorgänger schon geschrieben hat, brauchst du eigentlich immer eine Abbruchbedingung wo die Rekurrenz endet...