Sortieralgorithmus in O(log n)?
Gibt, oder gibt es einen (möglichen) Ansatz für einen Sortieralgorithmus der eine Komplexität von O(log n) hat? Bedeutet gleichzeitg, man durchläuft nicht einmal die gesamte Liste O(Konstante log n) wäre auch akzeptabel.
Nicht O(n log n)!
6 Antworten
Um beliebige Zahlen zu sortieren ist O (n log n) absolutes Minimum.
Wenn du aber Zahlen zwischen 1 und 10 sortieren willst dann geht das in O(n).
Darunter kann logischerweise nicht gehen, da du bei O(log n) nicht mal jedes Element ansehen kannst, dann kannst du es auch nocht einsortieren.
Best case geht natürlich mit O(n).
Der Algorithmus muss aber auch ab und zu die anderen n!-1 Permutationen ordnen können :)
Und dann gibt es auch sau ungünstige Konstellationen.
Wenn es sortiiert ist musst du nicht sortieren. Wir reden hier immer Worst-Case ^^
Wenn du die Zahlen von 1 bis 10 hast - wegen mir auch beliebige Zahlen zwischen 1 und 1e10000 - bekommst du das auch in O(n) im Worstcase sortiert.
Siehe:
das k geht aber gegen Unendlich bzw. Datentyplänge
Ne, k kannst du in den Fällen als 1 annehmen - den Algorithmus ausführen gänge logischerweise auch nicht, hättest du alle Resourcen des Universums. Laufzeit ist trotzdem O(n).
Du solltest dir dringend noch einmal die O-Schreibweise anschauen - denn da fehlt noch ein bisschen grundlegendes Verständniss.
O(Konstante log n) wäre auch akzeptabel.
O(c * n) ist exakt das gleiche wie O(n).
Konstanten werden bei der O-Schreibweise schlicht und einfach weggelassen.
Bedeutet gleichzeitg, man durchläuft nicht einmal die gesamte Liste
Und spätestens da solltest du feststellen, dass Sortieren in log n absoluter Schwachsinn ist.
Okay, hast irgendeine Folge, die du sortieren musst. Es gibt ein Element x, dass beim Sortieren nicht angeschaut wird. Der Algorithmus verhällt sich also gleich, egal was das x ist.
Wohin sortierst du das x?
Sortierst du das x in die Mitte oder ans Ende, wähle ich das x kleiner als jede andere Zahl -> Algorithmus funktioniert nicht.
Sortierst du das x an den Anfang, wähle ich das x größer als jede andere Zahl -> Algorithmus funktioniert nicht.
=> Gezeigt: Sortieren in <O(n) kann nicht klappen.
Es gibt einen Unterschied zwischen O(nahe Unendlich log n) und O(log n), nur weil man es kürzen kann, heißt es nicht das die Konstanten wertlos sind, frag dich sonst einmal wieso Quicksort schneller als Mergesort ist bei sehr großen n, obwohl beides O(n log n) hat bzw. Quicksort sogar O(n^2) im Worst-case
Was ist denn nahe Unendlich? Ne Millionen? Na, quadrieren wir mal. Sind wir der Unendlichkeit auch nur ein Stück näher gekommen? Wohl kaum.
Quicksort hat sich gezeigt, dass es in Realität realen Bedingungen häufig schneller ist. Dies ist aber unter anderem abhängig von:
* Optimiering
* Verwendete Hardware
* Qualität der Eingabe (z.B. Sortierungsgrad)
* ...
Das Quicksort bei großen Eingaben immer schneller ist, ist i.A. nicht richtig. Und unabhängig davon interessiert das bei O Betrachtungen nicht.
Und ja: Schreibst du O(log n) erlaubst du automatisch auch O(100000^100000 log n). So einfach.
theoretisch wäre das quantentheoretisch möglich .
etwas gleichzeitig zu sortieren
Hier kannst du einen Sortieralgormus wählen:
https://de.wikipedia.org/wiki/Kategorie:Sortieralgorithmus
...oder auf Englisch. Vorsicht, O(log n) Algorithmen benötigen viele Prozessoren.
>> Vorsicht, O(log n) Algorithmen benötigen viele Prozessoren.
Das ist Blödsinn.
1. Laufzeit bei Algorithmen in 0- Schreibweise hat nichts, also absolut nichts, mit der Anzahl verwendeter Prozessoren bei einer Ausführung zutun.
2. Du kannst so viele Prozessoren hinstellen wie du willst. Von O(n) auf O(log n) kommst du deshalb trotzdem nicht.
Wenn du bestimmte Sachen über die Liste weißt, ist das denkbar, aber kein solcher Algorithmus wird für gewöhnliche Probleme praktikabel sein.
Nur wenn es schon sortiert ist, ist es O(n), naja wirklich "sortieren" ist dies nicht ;)