Erklärung der Median der Medians Algorithmus

Den Median of medians Ansatz ist sehr beliebt in quicksort Art der Partitionierung algorithmen liefern eine ziemlich gute Drehpunkt, so dass es Partitionen des Arrays gleichmäßig. Seine Logik ist in Wikipedia:

Den gewählten Drehpunkt ist sowohl kleiner als und größer als die Hälfte der Elemente in der Liste der Mediane, die etwa n/10 Elemente (1/2 * (n/5)) für jede Hälfte. Jedes dieser Elemente ist ein median von 5, so dass es weniger als 2 andere Elemente und mehr als 2 andere Elemente außerhalb des Blocks. Daher werden die pivot ist weniger als 3(n/10) Elemente außerhalb des Blocks, und mehr als die anderen 3(n/10) Elemente außerhalb des Blocks. Damit die gewählten median teilt die Elemente irgendwo zwischen 30%/70% und 70%/30%, die versichert worst-case-lineares Verhalten des Algorithmus.

Kann jemand erklären, es ein bisschen klar für mich. Ich finde es schwierig, die Logik zu verstehen.

InformationsquelleAutor SexyBeast | 2012-09-22

  1. 14

    Denken Sie an die folgenden zahlen:

    5 2 6 3 1

    Den median dieser zahlen ist 3. Nun, wenn Sie haben eine Reihe n, wenn n > 3 ist, dann ist es größer als mindestens die Hälfte der oben genannten zahlen. Wenn n < 3, dann ist es kleiner als mindestens die Hälfte der oben genannten zahlen.

    So, dass ist die Idee. Das heißt, für jeden Satz von 5 zahlen, erhalten Sie Ihren median. Jetzt haben Sie n /5 zahlen. Dies liegt auf der Hand.

    Wenn man den median der zahlen (nennen wir es m), es ist größer als die Hälfte und kleiner als die andere Hälfte (durch definition von median!). In anderen Worten, m größer ist als n /10 zahlen (die selbst wurden Mediane der kleine 5-Elemente-Gruppen) und größer als der andere n /10 zahlen (die wurden wieder Mittelpunkte von kleinen 5-Elemente-Gruppen).

    In dem obigen Beispiel haben wir gesehen, dass, wenn der median k und Sie haben m > k, dann m ist auch größer als die 2 anderen Nummern (das waren Sie selbst, die kleiner als k). Dies bedeutet, dass für jede dieser kleineren 5-Elemente-Gruppen, in denen m war größer als Ihre Mittel, m ist auch größer als die beiden anderen zahlen. Dies macht es mindestens 3 zahlen (2 zahlen + den median selbst) in jedem dieser n /10 kleine 5-Elemente-Gruppen, die kleiner sind als m. Daher m ist zumindest größer als 3n/10 zahlen.

    Ähnliche Logik für die Anzahl der Elemente m ist größer als.

    Nur noch eine Frage, wie funktioniert diese Methode garantiert, dass diese Nummer wird der median? Der median ist eine Zahl, die eine Partitionierung des Arrays in der oberen und unteren Hälfte. Also, was bedeutet das 30-30-70 Abbildung zu bedeuten?
    Gut, dann ist der median in der Mitte, aber m (im text oben) ist nicht der median aller zahlen. Es ist der Mittelwert von nur 1/5 der zahlen (die selbst gemittelten Werte kleiner 5-Elemente-Gruppen). Lesen Sie den letzten Absatz, mit mehr Aufmerksamkeit. Am Ende, wo es wird gefolgert, dass m größer ist als mindestens 3n/10 zahlen, gut übersetzt m größer ist als mindestens 30% der zahlen. Also am Ende geht es wie m größer ist als mindestens 30% und kleiner als mindestens weitere 30%. Es gibt 40% übrig, die wir nicht sicher sind.
    Dann kommen, wie es gibt eine 50-50-partition im Durchschnitt? Die 50-50-partition ist gegeben durch die normale median, richtig?
    Es gibt nicht 50-50 partition im Durchschnitt. Es gibt immer irgendwo zwischen 30-70 und 70-30 (vielleicht könnte man sagen, dass 50-50 im Durchschnitt?), aber das ist nicht der Punkt. Für quicksort zu geben O(nlogn) Zeit, die Komplexität, die es braucht, um in der Lage sein zu teilen das array in Partitionen proportional zu der Größe des Arrays. Das ist es, was den logn Rekursionstiefe. 30-70 division gibt bereits einen 3n/10 und 7n/10 division, die proportional zur n. So, obwohl es nicht eine perfekte 50-50 ist, wird es noch Ertrag logarithmische Rekursionstiefe (außer es ist nicht log im base 2, base 10/7)

    InformationsquelleAutor Shahbaz

  2. 3

    Erklärung der median - der - Mediane-Algorithmus zum finden des k-TEN größte ganze Zahl aus n kann auch hier gefunden werden: http://cs.indstate.edu/~spitla/Präsentation.pdf

    InformationsquelleAutor totjammykd

Schreibe einen Kommentar