Aufwand von Divide and Conquer
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 an Conquer
blöde frage, wie kann man den aufwand einer divide and conquer rekursion berechnen bzw. die rekursion auflösen bsp.
T(n) = n-1 + T(n/2) ???
einfach einsetzen … dann schaun was sich bildet und daraus ne allgemeine lösung ableiden…
T(n) = n - 1 + n/2 - 1 + T(n/4)
→ T(n) = n - 1 + n/2 - 1 + n/4 - 1 + T(n/8)
und so weiter…
also kommt raus : T(n) = (n / 2^(n - 1)) - n … oder? naja war jetzt auf die schnelle…
nicht ganz.
du halbierst in jedem Schritt. also bist du nach log(n) schritten bei n=1
schätze jetzt mal T(1):=c (const)
Also für Potenzen von 2:
T(n) = c + (Summe_(von i=1)^(bis log(n)-1) n/(2^i) )- log(n)*1 =
(man summiert bis log(n)-1, weil bei n/ 2^log(n) =1 gilt)
= c + (1- (1/2)^(log (n) -1))/(1/2) - log(n)
(die Gleichung hält mit der geometrischen Summe)
warum stimmt das?
das c kommt aus der Startbedingung.
die summe kommt aus dem (n/2) teil.
das -log(n) kommt aus dem konstantem Glied.
ups, ok hab die summe vergessen…
das letzte Glied könnte auch -(log(n) - 1) sein.
Bin mir jetzt nicht ganz sicher
Das kann man doch einfacher mit dem Master-Theorem lösen!
a<b: Komplexität O(n)
Ich habe das ganze jetzt auch ausgerechnet … es kommt am Ende
2n-logn-2 raus
=> O(n) :*)
Hab ich auch raus
Das kann man aber allgemein nicht sagen, denn für t(n) = t(n/2) +c gilt ja auch a<b und die Komplexität ist O(log n).
doch … kann man!
laut Master-Theorem heißt es:
falls a=b^l => O((n hoch l)logn) das bedeutet hier … l ist in unserem Fall =0, da wir die Form n^l*c = c haben
=> genauer 1=2^0 => 1=1 => a=b^l = O((n hoch 0)logn) => O(logn)
Zusatz:
laut Master-Theorem musst natürlich nicht a und b vergleichen, sondern
a und b hoch l.
Du vergleichst a und b nur dann, wenn du die Form c*n hast … ist ja klar, denn aus n hoch l => l=1
daraus folgern wir weiter ab … Vergleich von a und b hoch 1 … und das ist genau das gleiche wie der Vergleich von a und b 
ICh hoffe das war jetzt klar.
noch allgemeiner kann man bei einer Rekursion der Form t(n) = a t(n/b) + cg(n) auch a und g(b) vergleichen, das deckt dann alle Fälle mit ab.
ja genau so hab ich das auch gemacht … wollte nur sagen, dass aus a < b nicht automatisch O(n) folgt, sondern dass man sich da das Master Theorem anschaun muss … war ein Missverständnis
yep … das klingt gut 
Ach ja, nicht dass mich jemand falsch versteht, bzw dann wegen mir falsche Ergebnisse bekommt: Natürlich wird dabei dann auch das Ergebnis zu
| Theta(g(n)) für a<g(b)
T(n) ∈ | Theta(g(n)*log(n)) für a=g(b)
| Theta(n[sup]log[sub]b/sub[/sup]) für a>g(b)