O(log n!) wirklich besser als O(n * log n) ?
-
n Elemente nacheinander in einen leeren Binärbaum einfügen ist vermutlich im Mittel
log 1 + log 2 + ... + log (n-1) + log n = log(n!)Ist das besser, als alle Elemente in eine Liste zu tun und diese am Ende zu sortieren O(n * log n). Oder ist das nur besser, wenn man zu jedem Zeitpunkt eine sortierte Datenstruktur braucht und amsonsten schlechter?
Wie kann man diese beiden Größenordnungen vergleichen?
n * log n = log n + log n + ... + log n (n-mal)
log n! = log 1 + log 2 + ... + log n (n-mal)
Das zweite sieht günstiger aus, aber ist eine der beiden Ordnungen echt größer, oder kann n * log n mit günstigerem konstanten Faktor besser sein?
-
Ich glaub die waren beide gleich (im O-Kalkül). Stand bei mir mal irgendwo mal auf nem Übungsblatt.
-
Ok, danke.
-
Die eine Richtung sieht man ja recht leicht, die andere Richtung sieht man mit der Stirling-Formel. Die gibt ne Abschätzung für n!
MfG Jester
-
Ja, kann man nachvollziehen. Jetzt fällt's mir auch wieder ein, dass es bei uns so was ähnliches schon mal in der Vorlesung gab. Da war zwar kein n * log n (also log(n^n) drin, aber es waren Elemente zweier verschiedener Komplexitätsklassen, die durch das Logarithmieren zu Elementen der gleichen Komplexitätsklasse wurden. Immer wieder faszinierend, auch wenn ich jetzt etwas geändert habe, so dass ich nur noch das kleinste Element brauche.
