Informatiker Board | Druckvorschau: Laufzeitbestimmung bei rekursiver Gleichung

Geschrieben von AufgeschmissenerGast am 08.05.2016 um 17:49:

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

Geschrieben von eulerscheZahl am 08.05.2016 um 18:04:

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]$

Geschrieben von AufgeschmissenerGast am 08.05.2016 um 18:16:

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]

Geschrieben von eulerscheZahl am 08.05.2016 um 18:24:

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.

Geschrieben von AufgeschmissenerGast am 08.05.2016 um 18:31:

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.

Geschrieben von eulerscheZahl am 08.05.2016 um 18:41:

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?

Geschrieben von AufgeschmissenerGast am 08.05.2016 um 18:49:

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?

Geschrieben von eulerscheZahl am 08.05.2016 um 18:52:

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

Geschrieben von AufgeschmissenerGast am 08.05.2016 um 18:57:

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.