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.
klausur herbst 2003 III-6 d)
Irgendwie ist es komisch bei der d)
versteh nicht ganz wie Vcreate(n) element von O(n) sein kann. Kann mir da jemand helfen? Ich dachte erst es ist ein Tippfehler weil doch log von n zu 2 doch summiert irgendwas mit nlog n gibt und
log von n/i zur basis 2 auch nix bringt.
Oder lieg ich falsch?
also die Summe kann man ja aufdröseln in
2* Summe von i=1 bis n über log(n) - 2* Summe Summe von i=1 bis n über log(i)
die Summe über log(n) is witzlos, weil man das log(n) vor die Summe ziehen kann - da kommt 2* n log(n) raus
die Summe über log(i) is gemein
Da schätzt man ab, dass die Summe ln(i) größer gleich dem ∫ ln(i) ist.
Summer i=1 bis n über log(i) = Integral von 1 bis n ∫ ln(i) / ln(2) dx
Stammfunktion dafür ist 1/ln(2) * [x * ln(x) - x] von 1 bis n
ergibt 1/ ln(2) * (n*ln(n) - n - 0 + 1)
damit ersetzt man die Summe von oben und erhält:
2n log(n) - 2n log(n) + 2/ ln(2) * (n-1)
das n log(n) fliegt raus und es bleibt noch n übrig - also O(n)
PS.: Nachzulesen in “Grundlegende Algorithmen” Seite 52
Schau mal hier, da sind noch ein paar mehr Summenformeln, aber auch die für [size=16]Σ[/size][i=1 bis n] log(i)
ja ok, aber mit log(n!) wäre man an der Stelle nicht weitergekommen. Entweder weiß man dass das irgendwann auch nlog(n) wird mit Stirling oder es bleibt dann 2nlogn - 2log(n!) übrig. Ich seh dem nicht an, dass es sich aufhebt.
hmm - da könnte ich jetzt auf Anhieb auch nur sagen dass es größer 0 ist, weil 2nlogn = 2log(n[sup]n[/sup]) <= 2log(n!)