| Die letzten 9 Beiträge |
| 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. |
| eulerscheZahl |
T(n) = 4 T(n/2) + ... |
| 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? |
| 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]](http://www.matheboard.de/latex2png/latex2png.php?\frac{16}{15}n^3) , die ersten beiden Summanden machen alleine schon ![[latex]\frac{17}{16}n^3[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\frac{17}{16}n^3) ).
Sind in deinem Bild die Zeiten rechts (oberhalb des ![[latex]\mathcal{O}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\mathcal{O}) ) klar? |
| 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.
AufgeschmissenerGast hat dieses Bild (verkleinerte Version) angehängt:
|
| 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.
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
|
| 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]](http://www.matheboard.de/latex2png/latex2png.php?n^3 + 4 * ( (n/4)^3 + 4 * ( (n/16)^3 + 4 * ( ( n/64)^3 ...) |
| 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]](http://www.matheboard.de/latex2png/latex2png.php?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)
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]](http://www.matheboard.de/latex2png/latex2png.php?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}) |
| 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 |
