Rekurrenzgleichung Lösen

Question

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?

Answer 1

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#

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#

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...

Comments

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

Es gibt auch ein Video dazu: