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.
A17 oder H2004/H2002
Aufgabe 17: Entscheidungsbaum f¨ur Merge
[Klausuraufgabe Herbst 2002 und Herbst 2004]
Der Sortieralgorithmus Mergesort beruht auf einer Prozedur merge, die aus zwei sortierten
Listen [a1, a2, . . . , am] (mit a1 a2 . . . am) und [b1, b2, . . . , bn] (mit b1 b2 . . . bn) die
sortierte Liste der m+n Elemente {a1, . . . , am, b1, . . . , bn} (die der Einfachheit halber paarweise
verschieden sein sollen) konstruiert.
- Konstruieren Sie den entsprechenden Entscheidungsbaum f¨ur die Vergleichsoperationen von
merge im Fall m = 3, n = 2. - Wieviele Bl¨atter hat der Entscheidungsbaum in Abh¨angigkeit von m und n?
- Betrachten Sie speziell den Fall m = n: wie verh¨alt sich diese Anzahl der Bl¨atter aus a) in
Abh¨angigkeit von der Listenl¨ange n asymptotisch f¨ur n ! 1?
(Hinweis: verwenden Sie Stirlings Formel: n! (n/e)n · p2n) - Welche Folgerungen ergeben sich aus der asymptotischen Anzahlaussage f¨ur die Vergleichs-
Komplexit¨at von merge-Algorithmen?
dort hätte ich eine Frage zur 3
muss ich dort 4!/n! ausrechnen oder wie genau muss ich diese Aufgabe verstehen?
Hallo Bibi!
Einfacher ist es, Du ersetzt n! gleich durch n^n.
2n über n = (2n)! / ( (2n-n)!*n! ) = (2n)! / ( n! * n! )
Nun wendest Du das oben gesagte an, also n! verhält sich wie n^n
(2n)^2n / (n^n * n^n ) = 4^n*n^2n / n^2n = 4^n;
War das Deine Frage?
Herzliche Grüße,
Marco
n! verhaelt sich anders. aber das schreib ich morgen; im moment bin ich dazu nimmer faehig. der entscheidende punkt ist dass n! ~= (n/e)^n
mit enstprechender umformung (morgen 
) kann man ein niedrigeres Wachstumsverhalten erhalten. also vorsicht bei der behauptung
Ich hatte irgendwann in der Vorlesung aufgeschrieben, dass n! etwa wie (n/e)^n wächst und das wiederum wächst etwa wie n^n. Scheinbar doch nicht so zwanglos einsetzbar…
bin gespannt auf deine lösung,
gruß, marco
Also ich dachte immer, dass die Stirling-Formel so wäre:
n! ~ (n/e)[sup]n[/sup]√(2πn)
Kann man das wirklich so einfach alles rausstreichen?
Wächst (n/e)[sup]n[/sup] wirklich wie n[sup]n[/sup]? Und wenn ja, warum? Und wann kann ich Faktoren weglassen (von Konstanten mal abgesehen)?
@marco ja das war meine Frage bin mal gespannt auf was wir uns einigen was richtig ist 
also mittlerweile glaub ich nicht mehr so recht dran dass (n/e)^n so wächst wie n^n womöglich hab ich da was falsches notiert. (-: gut, dass man mich korrigiert, thx.
Okay, die Stirlingsche Formel (Quelle: Wikipedia) lautet:
n! ~ (n/e)n√(2πn)
Wenn man das jetzt verwendet, um (2n über n) zu berechnen, kommt bei mir raus:
(2n über n) ~ c*4^n / √n
wobei c ne Konstante ist. Wächst also fast wie 4^n, aber halt nicht ganz.
Übrigens wächst n! schwächer als n^n, was man ja auch an der Stirlingschen Formel sieht. Denn zwischen n^n und (n/e)^n besteht ein Unterschied von e^n, und das ist ziemlich groß.