Informatiker Board | Theoretische Informatik | Laufzeitbestimmung bei rekursiver Gleichung

Informatiker Board » Themengebiete » Theoretische Informatik » Laufzeitbestimmung bei rekursiver Gleichung

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Laufzeitbestimmung bei rekursiver Gleichung

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

AufgeschmissenerGast
unregistriert

Laufzeitbestimmung bei rekursiver Gleichung

Zitatantwort auf diesen Beitrag erstellen

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

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

08.05.2016 18:04

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

AufgeschmissenerGast
unregistriert

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:16

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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:

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 08.05.2016 18:26.

08.05.2016 18:24

AufgeschmissenerGast
unregistriert

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:

08.05.2016 18:31

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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?

__________________
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

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

08.05.2016 18:52

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

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Laufzeitbestimmung bei rekursiver Gleichung