Auswahl Schwarzes Brett Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
Autor |
Laufzeit Heapsort Verständnisproblem |
|
memuench
Neu  Dabei seit: 13.11.2019 Mitteilungen: 2
 |     Themenstart: 2019-11-13 17:44
|
Profil
Quote
Link |
rlk
Senior  Dabei seit: 16.03.2007 Mitteilungen: 10592
Aus: Wien
 |     Beitrag No.1, eingetragen 2019-11-13 18:10
|
Hallo memuench,
herzlich willkommen auf dem Matheplaneten.
 
\ In Deiner vorletzten Gleichung fehlt ein \theta. Die Ungleichungskette hat die Form \theta(n log n)<= sum(log(i),i=1,n-1)<=\theta(n log n) woraus die behauptet Gleichung folgt. Beachte, dass diese (Un)gleichungen im Sinne der Landau\-Notation zu verstehen sind, Terme die in o(n log n) liegen, werden dabei vernachlässigt.
Ich hoffe, das hilft Dir,
Roland
|
Profil
Quote
Link |
Kitaktus
Senior  Dabei seit: 11.09.2008 Mitteilungen: 6099
Aus: Niedersachsen
 |     Beitrag No.2, eingetragen 2019-11-14 07:43
|
Kleine Ergänzung:
Nicht nur Summanden kleinerer Ordnung sind vernachlässigbar, sondern auch konstante positive Vorfaktoren.
Aus $0.001n-1000\leq f(n)\leq 1000n+1000$ folgt immer noch $f(n)\in\Theta(n)$.
|
Profil
Quote
Link |
memuench
Neu  Dabei seit: 13.11.2019 Mitteilungen: 2
 |     Beitrag No.3, vom Themenstarter, eingetragen 2019-11-18 16:32
|
Hallo ihr beide,
Vielen Dank für die Erklärung, ich hatte verpeilt, dass die Faktoren -1 und +1 weggelassen werden können. Nun macht das alles schon mehr Sinn!
|
Profil
Quote
Link |
|