Baumsortierung: Zeitkomplexität

Warum ist die durchschnittliche Komplexität der Fallzeit von tree sortO(n log n)?Baumsortierung: Zeitkomplexität

Aus Wikipedia:

ein Element in eine binäre Suchbaum hinzuzufügen ist im Durchschnitt ein O (log n) Prozess (in O-Notation), n Elemente ein O so Zugabe (n log n) Prozess

Aber wir fügen nicht jedes Mal einen Gegenstand zu einem Baum von n Einzelteilen hinzu. Wir beginnen mit einem leeren Baum und erhöhen allmählich die Größe des Baumes.

So sieht es eher wie

log1 + log2 + ... + logn = log (1*2*...*n) = log n!

ich etwas fehlt?

Quelle

2016-08-02 rapt

Der Grund, warum O(log(n!)) = O(nlog(n)) ist eine zweiteilige Antwort. Erstens erweitern O(log(n!)),

log(1) + log(2) + ... + log(n)

Wir sind uns einig, dass hier log(1), log(2), und alle Zahlen bis zu log(n-1) sind jeweils weniger als log(n). Daher kann die folgende Ungleichung gemacht werden,

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)

Nun ist die andere Hälfte der Antwort hängt von der Tatsache, dass die Hälfte der Zahlen von 1 bis n größer als n/2. Das bedeutet, dass log(n!) wäre größer als n/2*log(n/2) auch bekannt als die erste Hälfte der Summe log(n!),

log(1) + log(2) + ... + log(n) => log(n/2) + log(n/2) + ... + log(n/2)

Der Grund dafür ist, dass die erste Hälfte des log(1) + log(2) + ... + log(n) ist log(1) + log(2) + ... + log(n/2), die weniger als n/2*log(n/2) ist, wie durch die erste Ungleichung bewiesen so durch Addieren der zweiten Hälfte der Summe log(n!), es kann gezeigt werden, dass es größer als n/2*log(n/2) ist.

Also mit diesen beiden Ungleichheiten zu erkennen, dass O(log(n!)) = O(nlog(n))

Quelle

2016-08-02 04:44:05

Warum ist die zweite Ungleichung für die O-Definition erforderlich? Außerdem glaube ich, dass die Erklärung in Wikipedia irreführend ist: In der Praxis ist die Komplexität log (n!). Die Tatsache, dass es nicht schlechter als log (n^n) werden kann, ist cool, aber wir können auch sagen, dass es nicht schlimmer als log (n^n^n) werden kann. – rapt

@rapt, weil nach der großen O-Notation die untere Grenze 'n/2 * log (n/2)' die gleiche wie 'nlog (n)' ist, dann hast du die Ungleichung 'O (nlog (n)) < = O (log (n!) <= O (nlog (n)) ' –

Das ist richtig, aber wenn ich mir die formale Definition der großen O-Notation anschaue, sieht es so aus, als ob die erste Ungleichung alles zeigt 'log (n!) = O (n log (n))' Jedenfalls ist es eine gute einfache Erklärung, die mich an einige Details erinnert und bestätigt hat, dass der aktuelle Wikipedia-Eintrag "Baumsortierung" nicht so genau ist. – rapt

O(log(n!)) = O(nlog(n)).

https://en.wikipedia.org/wiki/Stirling%27s_approximation

(Die Antworten müssen 30 Zeichen lang sein.)

Quelle

2016-08-02 04:07:10 wookie919

Sie müssen nicht für die Stirling nachgewiesen werden? Einfach Logarithmenregeln und O-Definition. Aber ich habe mich gefragt, warum es nicht üblich ist, in diesem Fall anzugeben, dass die Komplexität O ist (log n!). Oft wird die O-Notation verwendet, um "das ist in etwa die Anzahl der Operationen", obwohl es nicht korrekt ist. Mit anderen Worten, im allgemeinen Gebrauch kann ein Algorithmus von O (log n!) Besser sein als einer von O (n log n). – rapt

@rapt Ich denke, was Sie bekommen, ist, dass "log (n!)" Vielleicht eine schärfere Grenze als "n log (n)" ist. Aber in der Welt, wenn Big-O, ist das ganz einfach nicht der Fall. 'O (log (n!))' Ist tatsächlich gleich 'O (n log (n))' wie hier bewiesen: http://stackoverflow.com/questions/8118221/what-is-ologn-and-on-and-and -Stirling-Approximation Ich denke, der Grund dafür, dass "O (n log (n))" bevorzugt wird, ist, weil die Leute es leichter verstehen. – wookie919

Ja. Aber wie gesagt, die große O-Notation wird informell verwendet, um die tatsächliche Zeitkomplexität zu zeigen, die nicht so genau ist, da sie nur eine obere Grenze der Zeitkomplexität darstellt. Wie auch immer, es ist eine gute Antwort. Vielen Dank. – rapt

Antwort

Verwandte Themen