Welche Regeln gelten für die "Ω (n log n) Barriere" für Sortieralgorithmen?
Schrieb ich ein einfaches Programm, sortiert in O(n). Es ist sehr Speicher ineffizient, aber das ist nicht der Punkt.
Es nutzt das Prinzip hinter einem HashMap für die Sortierung:
public class NLogNBreak {
public static class LinkedListBack {
public LinkedListBack(int val){
first = new Node();
first.val = val;
}
public Node first = null;
public void insert(int i){
Node n = new Node();
n.val = i;
n.next = first;
first = n;
}
}
private static class Node {
public Node next = null;
public int val;
}
//max > in[i] > 0
public static LinkedListBack[] sorted(int[] in, int max){
LinkedListBack[] ar = new LinkedListBack[max + 1];
for (int i = 0; i < in.length; i++) {
int val = in[i];
if(ar[val] == null){
ar[val] = new LinkedListBack(val);
} else {
ar[val].insert(val);
}
}
return ar;
}
}
So gilt das als eine Art von O(n), obwohl es gibt das Ergebnis in einer funky-format?
InformationsquelleAutor der Frage Ryan Amos | 2011-08-23
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Direkt Ihre Frage zu beantworten:
Was ist das also Ω(n log n) - Schranke? Wo kommt es her? Und wie tun Sie es brechen?
Ω(n log n) - Schranke
Ω(n log n) - Schranke ist die Informations-theoretische untere Schranke für den average-case-Geschwindigkeit jedes Vergleich-basierten Sortier-Algorithmus. Wenn das nur Vorgänge, die Ihnen erlaubt, zu beantragen, um array-Elemente zu unterscheiden, ist die Durchführung eine Art von Vergleich, dann ist dein Sortier-Algorithmus können Sie nicht tun besser als Ω(n log n) im average-case.
Zu verstehen, warum dies so ist, denken wir über die Zustand des Algorithmus an jedem Punkt während der Ausführung. Wie der Algorithmus, der ausgeführt wird, erhält eine gewisse Menge an Informationen über die Art und Weise, dass die input-Elemente bestellt. Lassen Sie uns sagen, dass, wenn der Algorithmus hat einige Informationen X über die ursprüngliche Anordnung der Eingabe-Elemente, dann wird der Algorithmus im Zustand X.
Den Kern von Ω(n log n) argument (und einige Verwandte Argumente, wie ich später eingehen werde) ist, dass der Algorithmus hat die Fähigkeit, sich in eine große Anzahl von verschiedenen Zuständen auf, was der input ist. Nehmen wir an, für jetzt, dass der Eingang zu den Sortier-Algorithmus ist eine Matrix, die n verschiedene Werte. Da der Algorithmus kann nicht sagen nichts über diejenigen, die andere Elemente als die Art und Weise, die Sie bestellt haben, ist es eigentlich egal, was die Werte sortiert sind. Alles was zählt ist die relative Reihenfolge dieser n Elemente zueinander.
Nun zum wichtigsten Schritt - nehmen wir an, dass es f(n) einzigartige Art und Weise der Bestellung der n Eingabeelemente und meint, dass unsere Sortier-Algorithmus kann nicht in mindestens f(n) verschiedenen Staaten. Wenn dies der Fall ist, dann muss es zwei verschiedene Ordnungen der Elemente im array an, dass der Algorithmus immer Gruppen zusammen in der gleichen Zustand. Wenn dies geschieht, dann ist der Algorithmus Sortieren kann möglicherweise nicht richtig Sortieren die beiden Eingabe-arrays korrekt. Die Argumentation hinter diesem ist, daß, da der Algorithmus behandelt die beiden arrays identisch, was auch immer Schritte, die Sie verwendet, um die Reihenfolge der Elemente der ersten array werden die gleichen wie die Schritte, die Sie verwendet, um die Reihenfolge der Elemente des zweiten Arrays. Da die beiden arrays nicht die gleiche, es hat zumindest eine element in einem der beiden Fälle. Folglich wissen wir, dass der Sortieralgorithmus muss in der Lage sein zu bekommen in f(n) verschiedenen Staaten.
Aber wie kann der Algorithmus erhalten in diesen verschiedenen Zuständen? Gut, lasst uns darüber nachdenken. Zunächst der Algorithmus hat überhaupt keine Informationen über die Reihenfolge der Elemente. Wenn es der erste Vergleich (z.B. zwischen die Elemente A[i] und A[j]) der Algorithmus kann in einem der beiden Staaten - eine, wo Eine[i] < A[j] und A[i] > A[j]. Generell, jeder Vergleich, dass der Algorithmus macht, kann, im besten Fall, setzen Sie den Algorithmus in einer von zwei neuen Staaten basiert auf dem Ergebnis des Vergleichs. Wir können daher denken Sie an einen großen binäre Baumstruktur beschreiben, die besagt, dass der Algorithmus-in - jeder Staat hat bis zu zwei Kinder beschreiben, in welchem Zustand sich der Algorithmus wird in basierend auf dem Ergebnis des Vergleichs, der ' s gemacht. Nehmen wir einen beliebigen Pfad von der Wurzel den Baum zu einem Blatt, so erhalten wir die Reihe der Vergleiche, die am Ende immer durch den Algorithmus auf einer bestimmten Eingabe. Um zu Sortieren, so schnell wie möglich, wollen wir die geringste Anzahl der Vergleiche möglich, und so wollen wir diese Struktur haben, die kleinste Höhe möglich.
Jetzt wissen wir zwei Dinge. Zuerst, denke, wir können alle Staaten der Algorithmus kann als ein binärer Baum. Zweitens, dass binäre Baum hat mindestens f(n) anderen Knoten. Angesichts dieser, die kleinste mögliche binären Baum wir bauen können, muss die Höhe mindestens Ω(log f(n)). Dies bedeutet, dass, wenn es f(n) verschiedene Möglichkeiten der Bestellung der array-Elemente, wir haben, um mindestens Ω(log f(n)) Vergleiche im Durchschnittdenn sonst können wir nicht in genug unterschiedlichen Staaten.
Zum Abschluss der Beweis, dass Sie nicht schlagen kann Ω(n log n), beachten Sie, dass, wenn das array mit n Elementen, dann gibt es n! verschiedene Möglichkeiten der Bestellung der Elemente. mit Stirling ' s approximation haben wir log n! = Ω(n log n), und daher müssen wir mindestens Ω(n log n) Vergleiche im average-case für das Sortieren der Eingabe-Sequenz.
Ausnahmen von der Regel
In das, was wir gerade oben gesehen haben, sahen wir, dass, wenn Sie n array-Elemente sind alle Verschieden, Sie können nicht Sortieren Sie mit einem Vergleich Sortieren nicht schneller als Ω(n log n). Doch diese erste Annahme ist nicht unbedingt gültig. Viele arrays, die wir gerne Sortieren können dupliziert haben Elemente in sich. Angenommen, ich möchte zum Sortieren von arrays, die bestehen ausschließlich aus Nullen und Einsen, wie das array hier:
In diesem Fall ist es nicht wahr, dass es n! verschiedene Anordnungen von Nullen und Einsen der Länge n ist. In der Tat, es gibt nur 2n. Aus unserem Ergebnis vor, das heißt, wir sollten in der Lage sein zu Sortieren in Ω(log 2n) = Ω(n) Zeit, die mit einer rein Vergleich-basierten Sortier-Algorithmus. In der Tat, wir können absolut tun; hier ist eine Skizze, wie wir es tun würde:
Zu sehen, dass es funktioniert, wenn die 0 ist das erste element, dann das 'weniger' - array wird leer sein, die 'gleich' - array wird über alle Nullen, und in die, größere ' array wird über alle diejenigen. Verketten Sie setzt dann alle Nullen vor allen diejenigen. Ansonsten, wenn 1 ist unsere erste element, dann die
lessarray wird halt die Nullen, dieequalarray halten wird, diejenigen, diegreaterarray wird leer sein. Ihre Verkettung ist also alle Nullen, dann alle Einsen.In der Praxis, Sie würden nicht mit diesem Algorithmus (die Sie verwenden würden, ein zählen Sortieren, wie unten beschrieben), aber es zeigt, dass Sie tatsächlich schlagen Ω(n log n) mit einer Vergleichs-basierten Algorithmus, wenn die Anzahl der möglichen Eingaben für den Algorithmus ist klein.
Einige Vergleich-basierten Sortier-algorithmen bekannt, dass Sie sehr schnell auf Eingaben, die mehrere duplizierte Werte. Zum Beispiel, es ist bekannt, dass Quicksort mit einer speziellen Partitionierung Schritt nutzen können duplizierte Elemente im Eingabe-array.
Non-Vergleich Sortiert
Alle diese Diskussion angenommen hat, dass wir reden über den Vergleich-basierten Sortierung, wo die einzige zulässige operation auf array-Elemente ist ein Vergleich. Jedoch, wenn wir mehr wissen über das, was Elemente, die wir gehen, zu Sortieren, und können Operationen auf diesen Elementen, die über einfache Vergleiche, dann keine der oben genannten Grenzen halten mehr. Wir brechen den Start Annahmen, führte uns zu konstruieren einen binären Baum, der alle Staaten der Algorithmus, und es gibt also keinen Grund zu vermuten, dass diese Grenzen immer noch halten.
Zum Beispiel, wenn Sie wissen, dass die input-Werte stammen aus einem Universum, das nur hat |U| Elemente, dann können Sie Sortieren in O(n + |E|) Zeit mit einem cleveren Algorithmus. Starten Sie zunächst mit dem erstellen |U| verschiedene Eimerin die wir uns legen können, die Elemente aus dem ursprünglichen array. Dann iterieren über das array und verteilen alle Elemente des Arrays in die entsprechenden Eimer. Schließlich besuchen Sie jede der Perioden, beginnend mit dem Eimer holding Exemplare das kleinste element und am Ende mit dem Eimer mit Kopien der das größte element, dann verketten Sie zusammen alle die Werte, die Sie finden. Zum Beispiel, lasst uns sehen, wie Sortieren von arrays bestehend aus den Werten 1 - 5. Wenn wir diese starten-array:
Dann können wir diese Elemente in buckets wie diese:
Iteration über den Eimer und verketten Ihre Werte zusammen, ergibt dies:
welche, sicher genug, wird eine sortierte version des original-array! Die Laufzeit ist hier O(n) Zeit zu gehen und verteilen Sie die ursprünglichen array-Elemente in die buckets, dann O(n + |E|) Zeit zum iterieren über alle buckets setzen die Elemente wieder zusammen. Beachten Sie, dass wenn |U| = O(n), diese läuft in O(n) Zeit, brechen Sie die Ω(n log n) Sortieren Barriere.
Wenn Sie Sortieren zahlen, die Sie tun können, viel besser als dies durch die Verwendung radix sortdie läuft in O(n lg |U|). Wenn man sich mit primitiven
ints, lg |U| ist in der Regel 32 oder 64, so ist dies extrem schnell. Wenn Sie bereit sind, zu implementieren, die eine besonders knifflige an der Struktur der Daten, die Sie verwenden können, eine van Emde Boas-Baum zum Sortieren von ganzen zahlen von 0 bis U - 1 in Zeit O(n lg lg U), wieder durch ausnutzen der Tatsache, dass Ganzzahlen bestehen aus Gruppen von bits, die manipuliert werden können in Blöcken.Ebenso, wenn Sie wissen, dass Ihre Elemente sind strings, die Sie Sortieren können sehr schnell durch den Bau einer trie aus den Saiten, dann die Iteration über die versuche, erstellen Sie die Zeichenfolgen. Alternativ könntest du überlegen, die strings als zahlen geschrieben und in ein großes base (sagen wir, base 128 ASCII-text) und dann mit einem der integer-algorithmen zur Sortierung von oben.
In jedem dieser Fälle ist der Grund dafür, dass Sie schlagen können die Informationen-theoretische Schranke ist, dass man das brechen der Barriere ab Annahme, nämlich, dass Sie können gelten nur für Vergleiche. Wenn Sie behandeln können die input-Elemente als zahlen oder als Zeichenketten, als alles andere, dass zeigt mehr Struktur, alle Wetten sind aus, und Sie können Sortieren sehr effizient.
Hoffe, das hilft!
InformationsquelleAutor der Antwort templatetypedef
Genannt wird
Radix Sortund ja, es bricht die nlog(n) Barriere, die nur ein Hindernis auf demVergleich Modell. Auf der wikipedia-Seite verlinkt für den Vergleich Modell können Sie eine Liste der Sorten, die Sie verwenden, und ein paar, die dies nicht tun.Radix-sort sortiert, indem jedes element in einen Eimer, den Sie basierend auf der Wert-und dann die Verkettung aller buckets wieder zusammen am Ende. Es funktioniert nur mit Typen wie ganze zahlen, die eine endliche Anzahl von möglichen Werten.
Normalerweise eine radix-sort ist ein nicht-byte oder nibble zu einer Zeit zu reduzieren, die Anzahl der buckets. Siehe den wikipedia-Artikel über Sie, oder suchen Sie nach mehr info.
Ihr ' s auch gemacht, um zu Sortieren, negative zahlen und nur Speicher für die Eimer benutzt es, um ihn zu verbessern.
InformationsquelleAutor der Antwort Paulpro