Warum ergibt das n*log(n), Beweis über eine Laufzeit, in dem man eine Summe mit Integralen abgeschätzt hat?
Beweis:
Wie man die Integrale bildet ist verständlich, aber dann habe ich eine Abschätzung nach unten und eine nach oben, wie kommt man aber am Ende dann auf
n*log(n)?
Soll das "Theta" für die Heaviside-Funktion bzw. Theta-, Treppen-, Schwellenwert-, Stufen-, Sprung- oder Einheitssprungfunktion sein?
Asympotische Gleichheit heißt das. Also das Sei asympototisch gleich zu n*log(n)
3 Antworten
Sowohl die Obere als auch die Untere Abschätzung liegen in Theta(n*log(n)) (übung für dich: Versuche zu verstehen, wieso das gilt) wodurch der Term dazwischen auch in Theta(n*log(n)) liegt.
(n-1)*ln(n-1)-(n-1) ach jetzt habe ich es (n-1)*ln(n-1)-(n-1) additive Terme lass ich weg n*ln(n)-n, das -n darf ich auch weglassen und so habe ich n*ln(n)
Ist doch völlig Wurst, da die Logs zu unterschiedlichen Basen einen konstanten Faktor zueinander haben.
Du kannst sagen:
oder auch
wobei (x)_{n} Pochhammer-Symbol ist:
Das was bei Ihnen gemacht wurde ist einfach nur einschnüren bis man nur noch "eine allgemeine Lösungsgleichung" hat, wobei die Lösung nicht einmal immer stimmt..
Deine Umformungen Bringen nichts, da man damit nicht die gewünschte Abschätzung erhält.
Schaue Dir mal an, wie man die Basis eines Logarithmus wechselt. Du solltest erkennen können, daß n log_b n in theta (n log_c n) liegt und umgekehrt.
Und dann überlegst Du noch weiter, warum beide Abschätzungen in theta (n log n) liegen.
Ich verstehe garnicht wie der von ln zu log kommt.