Laufzeitbestimmung bei rekursiver Gleichung |
AufgeschmissenerGast unregistriert
|
|
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 17:49 |
|
|
AufgeschmissenerGast unregistriert
|
|
Danke für deine Antwort! Aber wie kommst du auf diese Summanden?
Ich dachte die ersten Summanden müssten so aussehen
|
|
08.05.2016 18:16 |
|
|
|
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 , die ersten beiden Summanden machen alleine schon ).
Sind in deinem Bild die Zeiten rechts (oberhalb des ) klar?
__________________ Syntax Highlighting fürs Board (Link)
|
|
08.05.2016 18:41 |
|
|
AufgeschmissenerGast unregistriert
|
|
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:49 |
|
|
AufgeschmissenerGast unregistriert
|
|
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.
|
|
08.05.2016 18:57 |
|
|
|