war ich die folgende Frage in einem Algorithmen Buch gegeben:Zufall Mergesort
Angenommen, ein Merge-Sort wird implementiert, um eine Datei an einer beliebigen Position zu spalten, sondern dann genau in der Mitte. Wie viele Vergleiche würden von einer solchen Methode verwendet, um n Elemente im Durchschnitt zu sortieren?
Danke.
Um Sie auf die Antwort zu führen, betrachten Sie diese spezifischere Fragen:
Angenommen, die Spaltung immer bei 10% oder 25% oder 75% oder 90%. In jedem Fall: Wie wirkt sich die Rekursionstiefe aus? Wie viele Vergleiche müssen pro Rekursionsebene durchgeführt werden?
Ich bin teilweise einverstanden mit @Armen, sie sollten vergleichbar sein.
Aber: Betrachten Sie den Fall, wenn sie in der Mitte geteilt sind. Um zwei Listen von Längen n zusammenzuführen, würden wir 2*n - 1 Vergleiche benötigen (manchmal weniger, aber wir betrachten es aus Gründen der Einfachheit als fest), wobei jeder von ihnen den nächsten Wert erzeugt. Es würde log2(n) Ebenen von Zusammenführungen geben, die uns ungefähr n*log2(n) Vergleiche gibt.
Betrachten wir nun den Zufallssplit-Fall: Die maximale Anzahl an Vergleichen, die zum Zusammenführen einer Liste der Länge n1 mit einer Länge n2 benötigt wird, lautet n1 + n2 - 1. Heiterer, die durchschnittliche Zahl wird nahe daran sein, denn selbst für die unglücklichste Aufteilung 1 und n-1 werden wir einen Durchschnitt von n/2 Vergleiche benötigen. Wir können also davon ausgehen, dass die Kosten für das Zusammenführen pro Level die gleichen sind wie im Fall.
Der Unterschied ist, dass in zufälligen Fall die Anzahl der Ebenen größer sein wird, und wir können davon ausgehen, dass n für die nächste Ebene wäre max(n1, n2) anstelle von n/2. Diese max(n1, n2) wird dazu neigen, 3*n/4, das gibt uns die ungefähre Formel
n*log43(n) // where log43 is log in base 4/3
zu sein, die uns
n * log2(n)/log2(4/3) ~= 2.4 * n * log2(n)
Dieses Ergebnis noch größer ist gibt als die richtige, weil wir, dass die kleine Liste ignoriert haben weniger Ebenen, aber es sollte nahe genug sein. Ich nehme an, dass die richtige Antwort die Anzahl der comparations im Durchschnitt kann verdoppelt
Sie verpflichtet einen oberen von 2n * H_ erhalten wird {n - 1} < = 2n ln n mit der Tatsache, dass Zusammenführen von zwei Listen Gesamtlänge n kostet höchstens n Vergleiche. Die Analyse ist ähnlich der von randomisiertem Quicksort (siehe http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf).
Angenommen, wir teilen eine Liste der Länge n in 2 Listen L und R. Wir laden das erste Element von R für einen Vergleich mit allen Elementen von L und das letzte Element von L für einen Vergleich mit alle Elemente von R. Auch wenn diese nicht exakt die exakten Vergleiche sind, die ausgeführt werden, ist die Gesamtzahl der Vergleiche, die wir berechnen, n wie erforderlich.
Dies behandelt eine Ebene der Rekursion, aber was ist mit dem Rest? Wir fahren fort, indem wir uns nur auf die "rechts-nach-links" -Vergleiche konzentrieren, die zwischen dem ersten Element von R und jedem Element von L auf allen Rekursionsebenen auftreten (aus Symmetrie wird dies die Hälfte der tatsächlich erwarteten Summe sein).Die Wahrscheinlichkeit, dass das j-te Element mit dem i-ten Element verglichen wird, ist 1/(j - i) mit j> i. Um dies zu sehen, beachte man, dass Element j genau dann mit Element i verglichen wird, wenn es das erste Element ist, das als "Teilungselement" aus der Menge {i + 1, ..., j} gewählt wird. Das heißt, Elemente i und j werden in zwei Listen aufgeteilt, sobald die Liste, in der sie sich befinden, auf ein Element von {i + 1, ..., j} aufgeteilt wird, und Element j wird für einen Vergleich mit i genau dann geladen Element j ist das Element, das aus dieser Menge ausgewählt wird.
Somit ist die erwartete Gesamtzahl von Vergleichen, an denen j beteiligt ist, höchstens H_n (d. H. 1 + 1/2 + 1/3 ..., wobei die Anzahl der Terme höchstens n - 1 ist). Summierung über alle möglichen j ergibt n * H_ {n - 1}. Dies zählte nur "rechts-nach-links" Vergleiche, so dass die letzte obere Grenze 2n * H_ {n - 1} ist.