Quicksort, um Median zu finden?

Question

Warum ist das schlimmste Szenario $ Mathcal {o} links (n^2 rechts) $, wenn er QuickSort verwendet, um den Median einer Reihe von Zahlen zu finden?

• Wenn Ihr Algorithmus ständig eine Zahl wählt, die größer oder kleiner als kleiner als alle Zahlen in der Liste würden Ihr Algorithmus nicht scheitern? Zum Beispiel, wenn die Liste der Zahlen lautet:

  $ S = (12,75,82,34,55,15,51) $

  Und Sie auswählen immer wieder Zahlen von mehr als 82 US -Dollar oder weniger als 12 US -Dollar, um Unterschiede zu erstellen. Würde Ihr Set nicht immer gleich groß bleiben?

• Wenn Ihr Algorithmus ständig eine Nummer auswählt, die Unterschützen von $ 1 $ erstellt, warum ist das schlechteste Fall $ mathcal {o} links (n^2 rechts) $? Wäre die Effizienz nicht linear, wenn man das gemäß dem bedenkt Master -Theorem, $ d> log_b a $?* (und ist daher $ mathcal {o} links (n^d rechts) $ oder spezifisch in diesem Fall $ mathcal {o} links (n rechts) $)

*Wenn $ D $ der Effizienzponent ist (dh linear, exponentiell usw.), ist $ B $ der Faktor, den die Größe des Problems bei jeder Iteration reduziert, $ A $ ist die Anzahl der Teilprobleme und $ k $ ist das Level . Vollständiges Verhältnis: $ t (n) = mathcal {o} links (n^d rechts) * ( frac {a} {b^d})^k $

Answer 1

Quicksort dient zum Sortieren. Der von Ihnen beziehe Algorithmus ist ein Auswahlalgorithmus, der als bekannt ist Schnellauswahl.

• Da Sie nur eine Nummer als Pivot auswählen können, die in der Liste der Listen -Fall Nr. 1 ist, passiert nie.
• Der schlimmste Fall ist, dass Sie kontinuierlich eine Nummer auswählen, die die Liste in zwei Listen unterteilt: eine Liste mit nur einem Element und einer Liste mit $ N-1 $ -Lementen. Wenn dies in jeder Iteration der Fall ist, schließen Sie nur ein einzelnes Element aus.

Also erster Iteration Sie machen $ n $ operations, zweite Iteration $ N-1 $ Operations, dritte $ N-2 $ Operations, ... Letzte Iteration 1 Operation.

Welches ist die Summe der ersten natürlichen Zahlen von $ n $:

$ 1+2+3+...+(n-2)+(n-1)+n = n (n-1)/2 $ operations = $ o (n^2) $