Entfaltung von rekursiven Funktionen

27.10.2013, 20:44	MarioK	Auf diesen Beitrag antworten »
Entfaltung von rekursiven Funktionen Hallo! Hab als Angabe: $\begin{eqnarray} T(1) = 2 \end{eqnarray}$ $\begin{eqnarray} T(n) = 2 T(\frac{n}{4}) +3 \end{eqnarray}$ Und muss das Beispiel mit Hilfe einer Entfaltung lösen. Ich hab dann immer eingesetzt und bin auf $\begin{eqnarray} T(n) = 2^{i}T(\frac{n}{4^{i} }) + \sum\limits_{k=0}^{n-1} 2^{i} 3 \end{eqnarray}$ gekommen Jetzt weiß ich erstmal nicht sicher, ob das stimmt. Ich hab dann aber noch die maximale Rekursionstiefe ausgerechnet, sodass T(1) rauskam, also für $\begin{eqnarray} i = log_{4}(n) \end{eqnarray}$ eingesetzt. Eingesetzt kommt dann raus: $\begin{eqnarray} T(n) = 2^{log_{4}n}T(\frac{n}{4^{log_{4}n}}) + \sum\limits_{k=0}^{n-1} 2^{log_{4}n}3 \end{eqnarray}$ WENN das stimmt, ist meine Frage, ob man das $\begin{eqnarray} 2^{log_{4}n } \end{eqnarray}$ irgendwie wegbekommt oder kürzen kann oder umschreiben oder so? Und wenns nicht stimmt, würde ich gerne wissen, wo der/die Fehler liegt/liegen ^^ mfg Mario
28.10.2013, 19:03	MarioK	Auf diesen Beitrag antworten »
Okay, habs jetzt so geändert, dass über dem Sigma ein n-2 steht, damit es für n=1 passt und 2 rauskommt. Keine Ahnung ob das so stimmt, bzw ob man dass so machen kann, dass eine Folge so aussieht: $\begin{eqnarray} \sum\limits_{i=0}^(n-2) k \end{eqnarray}$ Kann man das so machen? Damit die Folge gar nicht durchlaufen wird, wenn n=1 ist?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »