Laufzeitbestimmung bei rekursiver Gleichung

08.05.2016, 17:49

AufgeschmissenerGast

Laufzeitbestimmung bei rekursiver Gleichung

Hallo Leute,

Ich sitze hier an einem Arbeitsblatt und komme nicht sehr weit. Genauer gesagt finde ich nichtmal einen Ansatz. Ich soll die Laufzeit bestimmen von folgender Rekursionsgleichung:

T(n) = 1 wenn n = 1
T(n) = 4 * T(n/4) + n^3 wenn n > 1

Sie dürfen annehmen, dass n von der Form 4^k ist.

Wie gehe ich da jetzt ran? Ich habe versucht die einzelnen Aufrufe zu zählen und die Höhe des "Baumes" zu bestimmen aber irgendwie steh ich voll aufm Schlauch.

Wäre super, wenn mir einer auf die Sprünge helfen könnte

08.05.2016, 18:04

Auf diesen Beitrag antworten »

eulerscheZahl

Schreibe dir mal die ersten Summanden hin:
$[latex]T(n) = n^3 + 4 \cdot \left(\frac{n}{4}\right)^3+ 4^2 \cdot \left(\frac{n}{4^2}\right)^3+ 4^3 \cdot \left(\frac{n}{4^3}\right)^3 + \dots[/latex]$
lässt sich vereinfachen:
$[latex]T(n) = \sum\limits_{i=0}^\infty \frac{n^3}{4^{2i}} = \sum\limits_{i=0}^\infty \frac{4^{3k}}{4^{2i}} = \frac{1}{15}\cdot 4^{3k+2}[/latex]$

08.05.2016, 18:16

Auf diesen Beitrag antworten »

AufgeschmissenerGast

Danke für deine Antwort! Aber wie kommst du auf diese Summanden?

Ich dachte die ersten Summanden müssten so aussehen

[latex]n^3 + 4 * ( (n/4)^3 + 4 * ( (n/16)^3 + 4 * ( ( n/64)^3 ...[/latex]

[latex]n^3 + 4 * ( (n/4)^3 + 4 * ( (n/16)^3 + 4 * ( ( n/64)^3 ...[/latex]

08.05.2016, 18:24

Auf diesen Beitrag antworten »

eulerscheZahl

Die n/16 gibt es eindeutig öfter als 4 Mal.

Edit:
oder war es Absicht, dass mehr Klammer aufgehen als zu?
Wenn ja, kannst du den Faktor ja reinziehen und bist dann bei meiner Formel.

08.05.2016, 18:31

Auf diesen Beitrag antworten »

AufgeschmissenerGast

In einer Aufgabe, die so ähnlich war, also quasi als Beispiel auf einem Foliensatz diente, wurde nichtmal etwas umgestellt, berechnet oder ähnliches. Leider sind keine Beschreibungen dabei und deshalb verstehe ich nicht wie die darauf kommen.

Ich stelle das Bild mal ein.

Irgendwie sind die von der Rekursionsgleichung (oben) direkt auf die Laufzeit (unten rechts) gekommen.

08.05.2016, 18:41

Auf diesen Beitrag antworten »

eulerscheZahl

Die Baumhöhe habe ich einfach als unendlich angenommen, die letzten Faktoren fallen sowieso kaum ins Gewicht (ersetzt man 4^k wieder durch n, gibt das eine Laufzeit von $[latex]\frac{16}{15}n^3[/latex]$ , die ersten beiden Summanden machen alleine schon $[latex]\frac{17}{16}n^3[/latex]$ ).

Sind in deinem Bild die Zeiten rechts (oberhalb des $[latex]\mathcal{O}[/latex]$ ) klar?

08.05.2016, 18:49

Auf diesen Beitrag antworten »

AufgeschmissenerGast

Nicht wirklich. Also wenn ich mir die einzelnen Zeilen angucke, verstehe ich auch, wie sie auf die Zeiten rechts kommen.

Was ich jedoch auch nicht verstehe ist, wieso in der zweiten Zeile der Algorithmus 4 mal durchlaufen wird. Eigentlich wird er doch nur einmal für n/2 aufgerufen, und nicht 4 mal?

08.05.2016, 18:52

Auf diesen Beitrag antworten »

eulerscheZahl

T(n) = 4 T(n/2) + ...

08.05.2016, 18:57

Auf diesen Beitrag antworten »

AufgeschmissenerGast

Zitat:

Original von eulerscheZahl
T(n) = 4 T(n/2) + ...

Dann hab ich da wohl einen Denkfehler. Ich dachte, es wird einfach der Integer T(n/2) einmal berechnet und die Ergebniszahl mit 4 multipliziert.

Neue Frage »

Antworten »

Laufzeitbestimmung bei rekursiver Gleichung

Verwandte Themen