Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Divide and Conquer (ÜB A24.2) 2T(sqrt(n))+log(n)
Soo folgendes Problem:
2T(√n) + log(n)
wobei √n abgerundet wird und m = log n substituiert werden soll.
Ausserdem darf großzügig gerundet werden.
:wand:
Lösung: log(n) log(log(n))
aber warum?!
:vogel:
s(m) = O(m logm)
m = logn
=> Ruecksubst:
T(n) = O(log(n) log log(n))
weil durch Substitution:
m = logn => n = 2[sup]m[/sup]
T(m) = 2T(m/2) + log(2[sup]m[/sup])
=T(m) = 2T(m/2) + m
→ Masterformel für Laufzeiten: (oder nochmal substituieren und lösen)
T(m) ∈ Theta(m*log(m))
->resubst:
T(m) ∈ Theta(log(n)*log(log(n)))
fertig
HTH
und warum kann man die Wurzel so einfach killen?
@Claudius wie kommst du auf
T(m)=2T(m/2) + m es muss T(m)=2T(m/2) + logm sein, oder nicht?
ich habe es so gemacht …
T(n)=2T(√n) + log(n)
(1) Subst: m=logn=> n=2^m
√n=n^1/2=> 2^m/2
T(2^m)=2T(2^m/2)+m Nun kann man die ganze Gleichung logarithmieren
T(m) = 2T(m/2) + log(m) (Zwischenlösung aus der Übung)
ich glaube aber eher T(m) = log2 * T(m/2) + log m =T(m/2) + log m
ist aber hier egal.
(Mit Masterformel funktioniert es hier nicht … ich weiß nicht warum?)
Nun kann man das rekursiv wie üblich lösen:
(2) Subst: m=2^k
T(2^k) = 2T(2^k-1) + k = 2^k + kΣ(von i=0 bis k-1) 2^i = (geom. Reihe)
= 2^k + k ((2^k)-1) = 2^k + k2^k - k = Resubst (2)
= m + mlogm - logm = Resubst (1) = logn + logn loglogn -loglogn
=> O(log(n)loglog(n))
gilt die Masterformel nur für die Form:
T(n) = T(n/2) + c*n oder kann man das genauso anwenden auf
T(2^n) = T(2^n/2) + c*n ?
ich glaube das geht auch, denn das war das Thema Divide and Conquer … sprich das Problem der größe n wird auf n/2 geteilt => es wäre egal, ob
das 2^n oder n ist … ist das richtig so? Die Problemgröße war ja n und nicht 2^n :-/
dann wäre der Schritt von Claudius natürlich richtig und besser :*)
Ich glaube mich zu erinnern, dass in der Vorlesung mal gesagt wurde, dass es nur um das Problem der Größe n gehe, welches durch DIVIDE geteilt wird.
Kann das jemand bestätigen oder ist das falsch?
Mit der Masterformel kannst du die Wachstumsordnung in Theta-Landau-Notation von Rekursionsgleichungen der Form
T(n) = a * T(n/b) + c*g(n)
bestimmen.
Und auf das T(m/2) komme ich, weil ja n=2[sup]m[/sup], d.h. √n = √(2[sup]m[/sup]) = 2[sup]m/2[/sup]
Wenn ich also substituiert habe, wird m in jedem Schritt halbiert.
und auf […] + m komme ich, weil log(2[sup]m[/sup]) kann ich abschätzen mit log[sub]2/sub = m