+1 Daumen
369 Aufrufe

T(n) = 2T(n/2) + nlogn

MIt dem Iterationsansatz löse man für T(1) = 1 die Rekurrenzgleichung

____________

Ich habe leider so eine art Aufgabe nie gemacht und weiß nicht ob mein Ansatz richtig ist / wie es weiter gehen würde

Da  n log n nichts rekursives hat würde ich es einfach erstmal weglassen und später bei der gleichung hinter dran hängen?

Deswegen nenne ich die Funktion mal solange F(n) und das ergebnis wäre dann später T(n) = F(n) + nlogn

T(1) = 1 = 2T(1/2)  + 1*log1 => 1/2 = T(1/2)

F(2) = 2T(1)  = 2

F(3) = 2T(3/2)   = ??

F(4) = 2T(2)  = 4

F(5) = 2T(5/2)  

F(6) = 2T(3)   = 4T(3/2)

F(7) = 2T(7/2)  

...

Irgendwie bringt mich das ganze ja nicht weiter?

von

1 Antwort

0 Daumen

Wie man so eine Rekursionsgleichung berechnen kann, zeigt der Iterationsrechner:

Lösung 1:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm##@Ni=0;@C0]=1;@N@Bi]=@P2,i);@Ci+1]=2*@Ci]+2*@Bi]*log(2*@Bi]);@Ni%3E22@N0@N0@N#

Bild Mathematik

Lösung 2:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm##@Ni=0;@B0]=@C0]=1;@N@Bi+1]=@P2,i+1);@Ci+1]=2*@Ci]+@Bi+1]*log(@Bi+1]);@Ni%3E22@N0@N0@N#

Bild Mathematik

Spalte aB entspricht Dein n und Spalte aC Dein T(n).

Und NEIN, den n*log(n) darf man nicht weglassen, da er mit jedem Schritt die Glieder der Folge vergrößert.

In der Aufgabe fehlt die Frage!!!!

Sollen Werte berechnet werden?

Vermutlich interessiert sich niemand für Werte, sondern es soll

https://de.wikipedia.org/wiki/Master-Theorem

angewendet werden...

von 5,6 k

Wie schon vermutet, interessieren sich die Aufgabensteller nicht für exakte Gleichungen, sondern nur für asymptotische Abschätzungen:

Bild Mathematik

Es gibt auch ein Video dazu:


Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

2 Antworten
Gefragt 1 Apr 2015 von Gast
0 Antworten
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community