Warum wird ein String O (n log n) sortiert?

Question

Mögliche Duplizieren:
Plain English explanation of Big O

In der Antwort auf eine Programmierung Puzzle sagte, es einen String Sortier O braucht Zeit (n log n). Wie wird das abgeleitet?

Hat jemand eine gute Referenz Link für Big O Ressourcen.

Dank

Answer 1

Eine Definition und einige Beispiele für Big O kann unter Verwendung einer Suchmaschine gefunden werden, z.B. hier:

:
• http://en.wikipedia.org/wiki/Big_O_notation

Eine Erklärung der Sortieralgorithmen basierend auf dem Vergleich von Elementen zusammen mit einer Erklärung für die auf der Anzahl der erforderlichen Vergleiche gebunden niedriger ist, sind hier zu finden

• http://en.wikipedia.org/wiki/Comparison_sort

Answer 2

Warum wird eine Zeichenkette O (n log n) sortiert?

Das Sortieren der Zeichen in einer Zeichenfolge ist nicht unbedingt O (n log n).

• O (n log n) ist der optimale Wert für eine comparison sort. Es ist auch die Komplexität der Standard-Sortierimplementierung vieler Sprachen. Es ist jedoch möglich, schlimmeres zu tun. Die Komplexität der Sortierung der Zeichen in einer Zeichenfolge hängt vom jeweiligen Algorithmus ab, den Sie zur Lösung dieser Aufgabe auswählen.
• In einigen Fällen ist es auch möglich, besser als O (n log n) zu arbeiten, indem ein Sortieralgorithmus verwendet wird, der keine Vergleichssortierung ist. Wenn Sie beispielsweise wissen, dass Sie eine ASCII-Zeichenfolge mit maximal 127 verschiedenen Zeichen haben, können Sie eine counting sort verwenden, die O (n) ist. Eine zählende Sortierung wäre auch für Unicode-Zeichenfolgen möglich, bei denen alle Zeichen in der Basic Multilingual Plane sind.