Die empirische Komplexität meiner "library sort" -Implementierung scheint nichts mit O zu vergleichen (n log n)
Ich habe kürzlich von der Bibliotheksortierung gehört, und da ich meine Schüler an der Einfügungssortierung (von der die Bibliotheksortierung abgeleitet wird), entschied ich, eine Übung für sie zu diesem neuen Thema zu erstellen. Das Tolle ist, dass dieser Algorithmus eine O (n log n) -Komplexität annimmt (siehe Titel Einfügesortierung ist O (n log n) oder der Text auf der Wikipedia-Seite über den obigen Link).
Ich bin mir bewusst, dass empirische Messungen nicht immer zuverlässig sind, aber ich habe versucht, mein Bestes zu geben, und ich bin ein wenig enttäuscht von der folgenden Handlung (blau ist die Bibliotheksortierung, grün ist der in-place-Quicksort von Rosetta Code ); vertikale Achsen ist die durchschnittliche Zeit, die als das Mittel vieler verschiedener Versuche berechnet wird; horizontale Achsen ist die Größe der Liste. Zufallslisten der Größe n haben ganzzahlige Elemente zwischen 0 und 2n. Die Form der Kurve sieht nicht wirklich etwas mit O (n log n) zusammen.
Hier ist mein Code (einschließlich des Testteils); habe ich etwas vermisst?
%Vor%Bearbeiten: Ich habe mehr Werte berechnet, bin zum Pypy-Interpreter gewechselt, um ein wenig mehr in derselben Zeit zu berechnen; hier ist eine andere Handlung; Ich habe auch Referenzkurven hinzugefügt. Es ist schwer, sicher zu sein, aber es sieht immer noch ein bisschen mehr wie O (n²) aus als O (n log n) ...
2 Antworten
Verknüpfen Sie mit einer PDF-Datei, die einen anderen Algorithmus für die so genannte Bibliothekssortierung auf Seite 7 verwendet:
Die PDF-Datei beschreibt eine hybride Zähl- und Einfügesortierung, die sich deutlich vom Wiki-Artikel unterscheidet, obwohl die PDF-Datei den Wiki-Artikel erwähnt. Aufgrund der Zählphase sind die so genannten Lücken genau so groß, dass das Zielarray die gleiche Größe wie das ursprüngliche Array hat und nicht um einen konstanten Faktor größer sein muss, wie im Wiki-Artikel erwähnt.
Beispiel: Eine Methode zum Ausführen, was die PDF-Datei eine Bibliotheksortierung in einem Array von ganzen Zahlen aufruft, wobei das höchstwertige Byte jeder ganzen Zahl verwendet wird, ein Array von counts == Array von Bucket-Größen wird erstellt. Diese werden durch akkumulative Summierung in ein Array von Startindizes für jeden Bucket umgewandelt. Dann wird das Array von Startindizes in ein Array von Endindizes für jeden Bucket kopiert (was bedeuten würde, dass alle Buckets anfänglich leer sind). Die Sortierung beginnt dann, für jede Ganzzahl aus dem Quell-Array, wählen Sie den Bucket über das höchstwertige Byte, führen Sie dann eine Insertion-Sortierung basierend auf den Start- und End-Indizes für diesen Bucket durch und inkrementieren Sie dann den End-Index.
In der PDF-Datei wird erwähnt, dass ein Hash-Typ verwendet wird, um Buckets für generische Objekte auszuwählen. Der Hash müsste die Sortierreihenfolge beibehalten.
Meine Vermutung ist, dass die Zeitkomplexität die Zeit ist, die Einfügungssortierungen durchzuführen, nämlich O (bucket_size ^ 2) für jeden Bucket, da der Durchlauf zum Erstellen der counts / bucket-Indizes linear ist.
Für Integer, da der größte Teil der Logik für das Zählen der Radix-Sortierung bereits vorhanden ist, könnte auch eine Multi-Pass-Funktion für die höchstwertige Byte-Zählen-Radix-Sortierung durchgeführt werden und die Einfügesortierung vergessen werden.
Zurück zum Wiki-Artikel, es gibt keine Erklärung, wie man eine leere Lücke erkennt. Unter der Annahme, dass kein Sentinel-Wert zur Darstellung einer leeren Lücke verfügbar ist, könnte ein drittes Array verwendet werden, um anzuzeigen, ob eine Position in dem zweiten Array Daten enthielt oder leer war.
Es gibt zwei Probleme mit Ihrem test() Code und nicht mit der library_sort() Implementierung:
- das Stoppen der Zeit beinhaltet die Erzeugung der Werte (inline), siehe Diagramm unten
- produziert viele gleiche Werte ("double vals" im folgenden Code) für begrenzte Reichweite mit zufälligen: Sie hatten wahrscheinlich nicht beabsichtigen, & gt; 20% wiederholte Werte mit
m = 2*i.
Tags und Links python time-complexity sorting