Logarithmische Sortieralgorythmen?
Hallo,
ich habe vor kurzen über die O Notation eines Algorithmus gelernt und da gibt es die O Notation O(log(n)) und da habe ich mich gefragt welche Sortieralgorythmen haben diese O Notation. Nach Recherche habe ich leider nichts gefunden. Kann mir da wer weiterhelfen?
2 Antworten
Kein Sortieralgorithmus kann in der Klasse O(log(n)) liegen. Selbst nicht im Bestcase, da jedes Element mindestens ein Mal geprüft werden muss. Somit ist die Laufzeit mindestens in O(n).
Außerdem können Vergleichsbasierte Sortieralgorthmen im Worst und Avrrage Case nicht besser als O(n*log(n)) sein. (Das ist bewiesen)
Radix sort hingegen ist in O(n), aber auch nur, weil es nicht Vergleichsbasierend ist und weil es Extra Speicher Benötigt.
So einen Algorithmus gibt es nicht.
Das bestmögliche Laufzeitverhalten eines Sortieralgorithmus ist O(n) und auch das nur dann, wenn die zu sortierenden Daten bestimmte Eigenschaften haben. Zum Beispiel bei gleichverteilten Daten und Verwendung von Bucketsort oder Countingsort.