Eine Rekursionsgleichung erstellen

Question

Aufgabe: Lösen Sie die Rekursionsgleichung

T(n) = 
                              2, falls n ≤ 1
           3T(n − 2) + 2, falls n > 1

Problem/Ansatz:

n	T(n)
0	2
1	2
2	8
3	8
4	26
5	26
6	80
7	80
8	242

Berechnet habe ich die werte wie am diesem gezeigt :
T(3) = 3T(3-2)+2
      = 3T(1)+2
      = 3*2+2
      = 8

Ich komme jetzt nur leider auf keine passende rekursionsgleichung. Ich weiß nicht wie die formel aussehen soll/muss damit sie bei je 2 werten denselben wert erreicht.

Comments

Was du hast ist doch eine Rekursionsgleichung. Oder suchst du stattdessen die explizite Bildungsvorschrift?

---

Ich soll mir daraus eine Formel herleiten an der ich die Zeitkomplexität messen/ errechnen kann

also vermutlich etwas in der form von zahl^n+2 da komme ich aber nicht weiter

---

Augenscheinlich sind alle Zahlen in der rechten Spalte um 1 kleiner als Dreierpotenzen.
Vielleicht könnte T(n) = 3^(n+2)/2 - 1, für gerade n und T(n) = 3^(n+1)/2 - 1 für ungerade n passen.

---

Vielleicht könnte T(n) = 3^(n+2)/2 - 1, für gerade n und T(n) = 3^(n+1)/2 - 1 für ungerade n passen.

Das passt, bzw. unabhängig von der Parität:$$T(n)= 3^{\left\lfloor n/2\right\rfloor + 1} - 1$$Btw.: wenn das eine Zeitkomplexität werden soll, würde ich den Algorithmus überdenken. Das ist indiskutabel zu hoch!

---

Könnten Sie vielleicht noch beschreiben wie Sie auf diese lösung gekommen sind ?

---

Könnten Sie vielleicht noch beschreiben wie Sie auf diese lösung gekommen sind ?

Intelligentes Probieren.

Es musste auf jeden Fall eine Formel sein, mit dem Ausdruck \(3^{n/2}\). Und da jeweils zwei hinter einander folgende Element der Folge gleich sind, muss es auch \(3^{\lfloor n/2\rfloor}\) heißen.

Und dann einfach mal hinschreiben:$$\begin{array}{ccc}n& T_n& 3^{\lfloor n/2 \rfloor}\\\hline 0& 2& 1\\ 1& 2& 1\\ 2& 8& 3\\ 3& 8& 3\\ 4& 26& 9\\ 5& 26& 9\\ 6& 80& 27\\ 7& 80& 27\\ 8& 242& 81\\ 9& 242& 81\\ 10& 728& 243\\ 11& 728& 243\end{array}$$Jetzt sieht man, dass noch \(1\) abgezogen werden muss, um die Folge zu treffen. Und anschließend muss der Index noch um \(2\) verschoben werden.

---

also kommt die 3 davon das in der rekursionsgleichung mit 3 multipliziert ? ich sehe aber nicht wieso es klar ist das n/2 gerechnet werden muss

---

also kommt die 3 davon das in der rekursionsgleichung mit 3 multipliziert ?

Ja

ich sehe aber nicht wieso es klar ist das n/2 gerechnet werden muss

Weil \(T_n\) nicht von \(T_{n-1}\), sondern von \(T_{n-2}\) abhängt. Die Verdreifachung geschieht erst nach zwei Schritten, statt nach einem.

Es gibt durchaus auch Verfahren, die explizite Form zu 'berechnen'. Aber bei derart einfachen Folgen, geht 'Intelligentes Probieren' schneller.

---

Können Sie mir auch helfen wie ich zu der formel die Komplexitätsklasse bestimme ?

---

Können Sie mir auch helfen wie ich zu der formel die Komplexitätsklasse bestimme ?

Kommt darauf an, um was es genau geht. Ich kenne Komplexitätsklasse nur von Algorithmen (aus der Informatik) deren Komplexität mit dem Landau-Symbol beschrieben wird. Wenn Dein \(T_n\) die Komplexität eines Algorithmus beschreibt, ist es unter praktischen Erwägungen viel zu groß!

Um was geht es denn genau?

---

Laut Aufgabe soll ich der Formel eine Groß-Theta klasse zuordnen.

---

Laut Aufgabe soll ich der Formel eine Groß-Theta klasse zuordnen.

Du meinst das \(\Theta(g)\) aus dieser Tabelle - oder? Da kann ich Dir wahrscheinlich nicht helfen.

---

Ja genau das meine ich. Das ist schade, aber Sie haben mir trotzdem sehr geholfen , Danke :)

Answer 1

Hallo

Schreib die Formel mal für gerade und ungerade n auf, also T(2n) und T(2n+1) dann siehst du die allgemeine Formel  für die 2 Fälle leicht, bzw für ihren Zusammenhang.

Gruß lul