Lösen von Rekursionsgleichung mit O-Notation

Question

Aufgabe: Lösen Sei die Rekursionsgleichung: T(n) = 3T(n/3) + 3n. Gehen sie von T(0) = T(1) = O(1) aus

Problem/Ansatz: Mein Ansatz ist T(n/3) = 3 * T(n/3/3) + 3n/3 = 3T(n/9) + n

Somit ergibt sich T(n) = 3 * (3T(n/9) + n) + 3n = 9T(n/9)+6n

Noch mal einsetzen: 9* (3T(n/9) + n) + 3n = 27T(n/27) + 12n

Muster erkennen 3^k * T(n/3^k) + … *n Ich erkenne das Muster nicht von 3n auf 6n und 12n, müsste dann da 9n rauskommen. Kann mir da jemand helfen, den Fehler zu finden

Answer 1

Man kann diese Rekursion z. Bsp. mit der Substitutionsmethode lösen. Setze dazu

$n= 3^k \Rightarrow T(3^k) = 3T(3^{k-1}) + 3^{k+1}$ mit $k =0,1,2,\ldots$

Nun schreibe noch zur Vereinfachung

$a_k = T(3^k) \Rightarrow \boxed{a_k = 3a_{k-1} + 3^{k+1} \text{ mit } a_0 = T(1)} \quad (1)$.

Hier noch eine kurze Zwischenbemerkung zu den Startwerten:

$T(0) =T(1) = O(1) \Rightarrow$ Nonsense!

Erstens benötigt die Rekursion nur einen Startwert $T(1)$. $T(0)$ macht hier keinen Sinn, da man die Rekursion aufgrund ihrer mathematischen Form nicht bei n=0 starten lassen kann.$O(1)$ bedeutet nur Beschränktheit, wobei $T(1)$ sowieso ein konstanter Wert ist.

Lösung der Rekursion (1):

(1) ist eine lineare inhomogene Differenzengleichung.

Die Lösung setzt sich zusammen aus der allgemeinen Lösung $h_k$ der homogenen Gleichung und einer partikulären Lösung $p_k$ der inhomogenen Gleichung:

$a_k = h_k + p_k$

Lösung der homogenen Gleichung:

$h_k = 3h_{k-1} \stackrel{\text{Hausaufgabe}}{\Longrightarrow} h_k = a_0 3^k$

Lösung der inhomogenen Gleichung:

Da die inhomogene Lösung den zusätzlichen Term $3^{k+1}= 3\cdot 3^k$ liefern muss, kann man hier den folgenden Ansatz wählen:

$p_k = c_k 3^k$ mit noch zu bestimmenden $c_k$.

Einsetzen in die inhomogene Gleichung gibt

$c_k 3^k = 3c_{k-1}3^{k-1} +3^{k+1} \Leftrightarrow c_k - c_{k-1}=3$

Wegen $a_0 = h_0 + c_0 \Rightarrow c_0 = 0$

Somit haben wir

$c_k - c_{k-1}=3, \: c_0=0 \stackrel{\text{Hausaufgabe}}{\Longrightarrow} c_k = 3k$

Also haben wir für die partikuläre Lösung

$p_k =c_k\cdot 3^k = 3k\cdot 3^k = k3^{k+1}$.

Die Rekursion hat also die Lösung:

$\boxed{a_k = a_03^k + k3^{k+1}}$

bzw. in der etwas mathematisch laxen Algorithmus-Schreibweise mit

$n=3^k \Leftrightarrow k = \log_3 n$:

$\boxed{T(n) = T(1)n + 3n\log_3(n)}$

Nachtrag zu deiner Frage:

Bis hier hin ist alles richtig:

$T(n) = 9 T\left(\frac n9\right) + 6n$.

Beim nochmaligen Einsetzen musst du in die Rekursionsgleichung $\frac n9$ einsetzen. Also

$T(n) = 9\left( 3T\left(\frac 13\cdot \frac n9 \right)+ 3\cdot \frac n9 \right) + 6n=27 T\left(\frac n{27}\right) + 9n$

Comments

Okay, vielen Dank. Die Anker waren so gestellt gemäß der Aufgabenstellung und wir sollen die Merhode Einsetzen und Muster erkennen, aber da ist ja bei mir irgendwo der Fehler, aber weiß nicht wo

---

Ich hab mal die Korrektur deines Fehlers beim Einsetzen als Nachtrag am Ende meiner Antwort ergänzt.