Ich arbeite an einer Quicksort-Variante, die auf dem Select-Algorithmus basiert, um ein Gut auszuwählen Drehelement. Herkömmliche Weisheit scheint zu sein, das Array in 5-Element-Blöcke zu teilen, den Median von jedem zu nehmen und dann rekursiv den gleichen Blockierungsansatz auf die resultierenden Mediane anzuwenden, um einen Median von Medianen zu erhalten.
Was mich verwirrt, ist die Wahl von 5-Element-Blöcken anstelle von 3-Element-Blöcken. Bei 5-Element-Blöcken scheint es mir, dass Sie n/4 = n/5 + n/25 + n/125 + n/625 + ... Median-von-5-Operationen durchführen, während Sie bei 3-Element-Blöcken n/2 = n/3 + n/9 + n/27 + n/81 + ... Median-von-3-Operationen durchführen. Da jeder Median-von-5 6 Vergleiche ist und jeder Median-von-3 2 Vergleiche ist, ergibt dies 3*n/2 Vergleiche mit Median-von-5 und n Vergleichen mit Median-von-3.
Kann jemand diese Diskrepanz erklären, und was könnte die Motivation für die Verwendung von 5-Element-Blöcken sein? Ich bin nicht vertraut mit den üblichen Praktiken für die Anwendung dieser Algorithmen, also gibt es vielleicht eine Möglichkeit, einige Schritte auszuschneiden und immer noch nah genug am Median zu sein, um einen guten Pivot zu gewährleisten, und dieser Ansatz funktioniert besser mit 5-Element-Blöcken ?
Der Grund ist, dass wir durch die Wahl von 3er-Blöcken die Garantie verlieren könnten, einen O (n) -Zeitalgorithmus zu haben.
Für Blöcke von 5 ist die Zeitkomplexität
T (n) = T (n / 5) + T (7n / 10) + O (n)
Für Blöcke von 3 ist es
T (n) = T (n / 3) + T (2n / 3) + 0 (n)
Sieh dir das an: Ссылка
Ich glaube, es hat damit zu tun, eine "gute" Trennung sicherzustellen. Die Aufteilung in Blöcke mit 5 Elementen gewährleistet eine Worst-Case-Aufteilung von 70-30. Das Standardargument lautet wie folgt: Von den n/5 -Blöcken ist mindestens die Hälfte der Mediane & gt; = Median der Mediane, daher hat mindestens die Hälfte der n/5 Blöcke mindestens 3 Elemente (1/2 von 5) & gt; = Median von Medianen, und dies ergibt eine 3n/10 Teilung, was bedeutet, dass die andere Partition im schlimmsten Fall 7n/10 ist.
Das gibt T(n) = T(n/5) + T(7n/10) + O(n) .
Seit n/5 + 7n/10 < 1 ist die Worst-Case-Laufzeit O (n) .
Bei der Wahl von 3-Element-Blöcken ist es also so: Mindestens die Hälfte der n/3 Blöcke hat mindestens 2 Elemente & gt; = Median-von-Medianen, daher ergibt sich eine n/3 Teilung, oder 2n/3 in der schlimmsten Fall.
Das gibt T(n) = T(n/3) + T(2n/3) + O(n) .
In diesem Fall n/3 + 2n/3 = 1 , so reduziert es sich im schlimmsten Fall auf O (n log n) .
Sie können Blöcke der Größe 3 verwenden! Ja, ich bin genauso überrascht wie du. Im Jahr 2014 (Sie haben 2010 gefragt) kam ein Papier, das zeigt, wie es geht.
Die Idee ist wie folgt: anstatt median3 , partition , median3 , partition , ... zu tun, tun Sie median3 , median3 , partition , median3 , median3 , partition , .... In der Arbeit wird dies "The Repeated Step Algorithm" genannt.
Also statt:
%Vor%bekommt man:
%Vor%Dieser Artikel ist Auswählen mit Gruppen von 3 oder 4 Takes Linear Time von K. Chen und A. Dumitrescu (2014, arxiv) oder Wählen Sie mit Gruppen von 3 oder 4 aus (2015, Homepage des Autors).
PS: Die schnelle deterministische Auswahl von A. Alexandrescu (von D-sprachiger Berühmtheit!), die zeigt, wie man das oben genannte sogar durchführt effizienter.
Tags und Links algorithm language-agnostic sorting quicksort median