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)?
![](https://images.gutefrage.net/media/user/LORDderANALYSE/1660346873164_nmmslarge__114_33_378_378_289f557699d4f9fbe40c41c853a42963.jpg?v=1660346873000)
Soll das "Theta" für die Heaviside-Funktion bzw. Theta-, Treppen-, Schwellenwert-, Stufen-, Sprung- oder Einheitssprungfunktion sein?
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
Asympotische Gleichheit heißt das. Also das Sei asympototisch gleich zu n*log(n)
3 Antworten
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
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.
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
(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)
![](https://images.gutefrage.net/media/default/user/5_nmmslarge.png?v=1438863662000)
Ist doch völlig Wurst, da die Logs zu unterschiedlichen Basen einen konstanten Faktor zueinander haben.
![](https://images.gutefrage.net/media/user/LORDderANALYSE/1660346873164_nmmslarge__114_33_378_378_289f557699d4f9fbe40c41c853a42963.jpg?v=1660346873000)
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..
![- (Mathematik, Informatik, Analysis)](https://images.gutefrage.net/media/fragen-antworten/bilder/480569283/0_big.png?v=1670353567000)
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
Deine Umformungen Bringen nichts, da man damit nicht die gewünschte Abschätzung erhält.
![](https://images.gutefrage.net/media/default/user/5_nmmslarge.png?v=1438863662000)
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.