Wie hoch ist die durchschnittliche Zeit für die schnelle Sortierung?

Question

Ich sehe eine google search zieht hier viel, aber es gibt viel Zweideutigkeit im Internet. Bitte nicht als Duplikat markieren.

Ich habe

gesehen

n log n 

und

n ln n 

und schließlich

n log(base2) n 

Einer der SO answers behandelt Big O als schlimmsten Fall und Zustände n^2. Worst Case ist in der Tat n^2, aber Big O bedeutet nicht Worst Case, also in diesem Sinne ist es hoch gewählt, aber falsch.

Um klar zu sein, möchte ich den durchschnittlichen Fall kennen und um klar zu sein, ist dies für Zeit-Komplexität.

Answer 1

In Mathematik, die Sie immer davon ausgehen, die Basis bis 10.

In der Informatik gleich ist, wenn die Basis aus dem Logarithmus weggelassen wird, diktiert Konvention, dass die Basis 2.

Bit of a gleich dumme Frage wirklich, ich bin überrascht, dass dein Lehrer das nicht angesprochen hat. Sie können jede der drei Big-O-Laufzeiten in Ihrem ursprünglichen Post verwenden, da sie alle dasselbe bedeuten.