0 Daumen
1,1k Aufrufe

Aufgabe:

Gib für die folgende Rekursionsgleichung eine geschlossene Form in θ-Notation an. Du kannst stets von n = 2k für k > 0 ausgehen.

T (n) = 3 * T (n - 1) + 1,   T (1) = 1


Problem/Ansatz:

T (n) = 3 * T (n - 1) + 1

= 3 * (3 * T (n -1 - 1) + 1) + 1)

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

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

= 3 * 3 * 3 (T (n - 3) + 1) + 1) + 1)

= 3³ * T (n - 3 * 1) + i=0313i \sum\limits_{i=0}^{3-1}{3^{i}}

n - i * 1 = 0

=> i = n

= 3n 3^{n} * T ( n - 1 * n) * i=0n13i \sum\limits_{i=0}^{n-1}{3^{i}}

= 3n 3^{n} * T (0) * i=0n13i \sum\limits_{i=0}^{n-1}{3^{i}}

= 3n 3^{n} * T (0) * 3(n1)+112 \frac{3^{(n-1)+1}-1}{2}

Ab hier weiß ich leider nicht weiter. Der Basisfall aus der Aufgabenstellung ist ja eigentlicht T (1) = 1. Aber ich komme hier komischerweise auf T (0).

LG

Marceline, The Vampire Queen

Avatar von

2 Antworten

0 Daumen

Deine Rechnungen stimmen nicht so ganz.

...= 3 * 3 * 3 ( T (n - 2 - 1) + 1) + 1) + 1=...

In dieser Zeile hast du die Klammerung nicht mehr richtig. Es muss wenn dann so hier aussehen:

T(n)=3T(n1)+1T(n1)=3(n2)+1T(n2)=3T(n3)+1T(n)=3(3(3T(n3)+1)+1)+1 T(n)=3\cdot T(n-1)+1\\ T(n-1)=3\cdot (n-2)+1\\ T(n-2)=3\cdot T(n-3)+1\\[10pt] T(n)=3\cdot(3\cdot(3\cdot T(n-3)+1)+1)+1

So deine Rekursionsgleichung zu lösen halte ich für etwas riskant, da man sich einfach zu schnell vergucken kann. Mache es stattdessen andersherum, indem du einfach mal die ersten n=1,2,3,4,5 zB mal anschaust:

T(2)=3T(1)+1=31+1=31+30T(2) = 3\cdot T(1)+1 = 3\cdot 1+1 = 3^1+3^0

T(3)=3T(2)+1=3(31+1)+1=32+31+30. T(3) = 3\cdot T(2)+1 = 3\cdot(3\cdot 1+1)+1 = 3^2+3^1+3^0.

Ich denke, ab hier sollte dann eine Struktur erkennbar sein, die du dann in eine hübsche Formel eintüten kannst, und sie nur noch per Induktion beweisen musst.

Edit: Das T(n)∈θ(3n) gilt, kannst du ja entsprechend mit der Landau-Definition nochmal verifizieren.

Avatar von 15 k

Tschaka hat doch t1=1 in seiner Herleitung verwendet. Du hast fälschlicherweise bei 0 angefangen zu zählen und nicht, wie es richtig ist, bei 1.

Danke, habs geändert.

@Marceline

Und wenn man es nun doch auf diese Art machen möchte, sähe das allegemein so aus:

T(n)=3T(n1)+1T(n1)=3T(n2)+1T(n2)=3T(n3)+1T(n3)=3T(n4)+1T(n)=3(3(3...3(3n1 malT(1)+1)+...+1)+1)+1=3(3(3...3(3n1 mal1+1)+...+1)+1)+1=3n1+...+30=k=0n13k=12(3n1)T(n)=3\cdot T(n-1)+1\\ T(n-1)=3\cdot T(n-2)+1\\ T(n-2)=3\cdot T(n-3)+1\\ T(n-3)=3\cdot T(n-4)+1\\[10pt] T(n)=\underbrace{3\cdot (3\cdot (3\cdot ...\cdot 3\cdot (3}_{n-1 \text{ mal}}\cdot T(1)+1)+...+1)+1)+1\\=\underbrace{3\cdot (3\cdot (3\cdot ...\cdot 3\cdot (3}_{n-1 \text{ mal}}\cdot 1+1)+...+1)+1)+1\\=3^{n-1}+...+3^0=\sum_{k=0}^{n-1} 3^k=\frac{1}{2}\cdot (3^n-1)

Und wenn wir schon dabei sind, ist hier noch die Klassifikation zu der Laufzeitfunktion:

Mit n_0=1 und α=1 ergibt sich

0T(n)=12(3n1)13nT(n)O(3n) 0\leq T(n)=\frac{1}{2}\cdot (3^n-1)\leq 1\cdot 3^n \Leftrightarrow T(n)\in \mathcal{O}(3^n)

Mit n_0=1 und β=1/4 ergibt sich weiter

T(n)=12(3n1)=123n12n1143nT(n)Ω(3n) T(n)=\frac{1}{2}\cdot (3^n-1)=\frac{1}{2}\cdot 3^n-\frac{1}{2}\stackrel{n\geq 1}{\geq} \frac{1}{4}\cdot 3^n \Leftrightarrow T(n)\in \Omega(3^n)

Also hat man insgesamt T(n)∈Θ(3n).

0 Daumen

Aloha :)

Du bist auf einem sehr guten Weg.tn=3tn1+1;t1=1t_n=3t_{n-1}+1\quad;\quad t_1=1Zum Entwickeln eines geschlossenen Ausdrucks für tnt_n betrachte die ersten Folgenglieder:t1=1t_1=1t2=3t1+1=3(1)+1=3+1t_2=3t_1+1=3\cdot(1)+1=3+1t3=3t2+1=3(3+1)+1=32+3+1t_3=3t_2+1=3\cdot(3+1)+1=3^2+3+1t4=3t3+1=3(32+3+1)+1=33+32+3+1t_4=3t_3+1=3\cdot(3^2+3+1)+1=3^3+3^2+3+1Jetzt kann man bereits vermuten, dasstn=3n1+3n2+3n3++30=k=0n13k=3n131        tn=3n12t_n=3^{n-1}+3^{n-2}+3^{n-3}+\cdots+3^0=\sum\limits_{k=0}^{n-1}3^k=\frac{3^n-1}{3-1}\;\;\Rightarrow\;\;\underline{t_n=\frac{3^n-1}{2}}Natürlich musst du das noch durch vollständige Induktion beweisen:

Verankerung bei n=1n=1:t1=1;3112=1t_1=1\quad;\quad\frac{3^1-1}{2}=1\quad\checkmark

Induktionsschritt nn+1n\to n+1:tn+1=3tn+1=33n12+1=3(3n1)2+22=3n+13+22=3n+112t_{n+1}=3t_n+1=3\cdot\frac{3^n-1}{2}+1=\frac{3\cdot(3^n-1)}{2}+\frac{2}{2}=\frac{3^{n+1}-3+2}{2}=\frac{3^{n+1}-1}{2}\quad\checkmarkDie Laufzeit ist also von der Ordnung Θ(3n)\Theta(3^n).

Avatar von 152 k 🚀

Danke für die Antwort. Mich irritiert nur, dass wir ja sozusagen für die n-te Zeile den Ausdruck

= 3n 3^{n} * T (0) * 3(n1)+112 \frac{3^{(n-1)+1}-1}{2}

bzw.

= 3n 3^{n} * T (0) * 3n12 \frac{3^{n}-1}{2} haben.

Aber in der Aufgabenstellung steht ja "Basisfall T (1) = 1." Diese Information haben wir ja jetzt gar nicht für den Lösungsweg verwendet. Ich komme hier immer auf T (0). Weil die allgemeine Form wäre ja

= 3i 3^{i} * T (n - i * 1) * 3(i1)+112 \frac{3^{(i-1)+1}-1}{2}

und T (n - i * 1) ergibt eben

n - i * 1 = 0

n = i.

Und T (n - n) wäre demnach 0. Also T (0) und nicht T (1). :(

Aloha :)

Direkt zu Anfang startet die Liste mit t1=1t_1=1. Anschließend pflanzt sich dieses t1t_1 immer weiter in die anderen tnt_n fort. Wenn man so will, hat t1=1t_1=1 sogar einen Ehrenplatz.

Du numerierst die tt's von 0 an durch, was aber keinen Sinn macht, weil der Algorithmus für n=0n=0 nichts zu tun hat, sodass t0=0t_0=0 sein muss.

Ein anderes Problem?

Stell deine Frage