Analyse von Mergesort

Wenn die Funktion merge in $\mathrm{\Theta }(n)$‍ Zeit läuft, wenn sie $n$‍ Elemente zusammenführt, wie können wir dann zeigen, dass mergeSort in $\mathrm{\Theta }(n{\log }_{2}n)$‍ Zeit läuft? Wir fangen an, indem wir über die drei Teile von Teile-und-Herrsche nachdenken und wie wir ihre Laufzeiten berücksichtigen können. Wir nehmen an, dass wir insgesamt $n$‍ Elemente im gesamten Array sortieren.

Betrachten wir die Teile- und Kombinations-Schritte gemeinsam: Die $\mathrm{\Theta }(1)$‍ Laufzeit für den Teile-Schritt ist vernachlässigbar klein im Vergleich zur $\mathrm{\Theta }(n)$‍ Laufzeit des Kombinations-Schritts . Also können wir die Größenordnung der gemeinsamen Laufzeit der beiden Schritte mit $\mathrm{\Theta }(n)$‍ angeben. Um etwas konkreter zu werden sagen wir, dass der Teile- und Kombinations-Schritt zusammen $cn$‍ Zeit in Anspruch nehmen, wobei $c$‍ eine Konstante ist.

Zur Vereinfachung gehen wir davon aus, dass wenn $n>1$‍ ist, dann ist $n$‍ immer gerade, also $n/2$‍ ist eine Ganzzahl. (Der Fall, in dem $n$‍ ungerade ist, ändert nicht das Ergebnis der Betrachtung in Bezug auf die Big-Θ Notation.) Damit ist die Laufzeit von mergeSort auf einem $n$‍ -Elemente Subarray das Doppelte der Laufzeit von mergeSort auf einem $(n/2)$‍ -Elemente Subarray (für den Eroberungsschritt) plus $cn$‍ (für die Teile- und Kombinations-Schritte).

Jetzt müssen wir die Laufzeit der beiden rekursiven Anrufe auf $n/2$‍ Elemente bestimmen. Jeder dieser beiden rekursiven Anrufe dauert doppelt solange wie die Laufzeit von mergeSort auf einem $(n/4)$‍ -Elemente Subarray (weil wir $n/2$‍ halbieren müssen) plus $cn/2$‍ zum Zusammenführen. Wir haben zwei Teilprobleme der Größe $n/2$‍, und jedes dauert $cn/2$‍ Zeit zum Kombinieren, und so ist die benötigte Gesamtzeit zum Kombinieren der Teilprobleme der Größe $n/2$‍ gleich $2\cdot cn/2=cn$‍.

Wir können die Kombinations-Zeit als "Baum" darstellen"

Informatiker zeichnen Bäume gerne auf den Kopf, also verkehrt herum wie natürliche Bäume wachsen. Ein Baum ist ein Graph ohne Zyklen (Pfade, die am gleichen Knoten beginnen und enden). Die Konvention ist, die Astgabeln in einem Baum als seine Knoten zu bezeichnen. Die Wurzel ist der Knoten ganz oben. Hier ist die Wurzel mit $n$‍ gekennzeichnet, also der Größe des Subarrays für das ursprüngliche $n$‍ -Elemente Array. Unterhalb der Wurzel sind zwei Kinder-Knoten, die jeweils mit $n/2$‍ markiert sind, um die Größen des Subarrays für die beiden Teilprobleme der Größe $n/2$‍ darzustellen.

Jedes der Teilprobleme der Größe $n/2$‍ sortiert rekursiv zwei Subarrays der Größe $(n/2)/2$‍ oder $n/4$‍. Weil es zwei Teilprobleme der Größe $n/2$‍ gibt, gibt es vier Teilprobleme der Größe $n/4$‍. Jedes dieser vier Teilprobleme kombiniert insgesamt $n/4$‍ Elemente, und so ist die Kombinations-Zeit für jedes der vier Teilprobleme $cn/4$‍. Zusammengefasst über die vier Teilprobleme sehen wir, dass die gesamte Kombinations-Zeit für alle Teilprobleme der Größe $n/4$‍ gleich $4\cdot cn/4=cn$‍ ist:

Wie geht das wohl für die Teilprobleme der Größe $n/8$‍ weiter? Es wird acht von ihnen geben. Die Kombinations-Zeit für jedes Teilproblem wird $cn/8$‍ sein, für eine Gesamt-Kombinations-Zeit von $8\cdot cn/8=cn$‍:

Im selben Maß in dem die Teilprobleme kleiner werden, verdoppelt sich die Anzahl der Teilprobleme auf jeder "Ebene" der Rekursion, wobei sich die Kombinations-Zeit halbiert. Die Verdopplung und Halbierung heben sich gegenseitig auf, und so ist die gesamte Verschmelzungszeit auf jeder Rekursionsebene $cn$‍. Irgendwann erreichen wir Unterprobleme der Größe 1: Dem Basisfall. Wir müssen dann $\mathrm{\Theta }(1)$‍ Zeit verwenden, um Subarrays der Größe 1 zu sortieren, denn wir müssen testen, ob $p<r$‍ ist, und dieser Test benötigt konstante Zeit. Wie viele Subarrays der Größe 1 gibt es? Da wir mit $n$‍ Elementen begonnen haben, muss es $n$‍ von ihnen geben. Da jeder Basisfall $\mathrm{\Theta }(1)$‍ Zeit dauert, nehmen die Basisfälle insgesamt $cn$‍ Zeit in Anspruch:

Jetzt wissen wir, wie lange das Zusammenführen für jede Teilproblemgröße dauert. Die Gesamtzeit für mergeSort ist die Summe der Zeit zum Zusammenführen aller Ebenen. Wenn es $l$‍ Ebenen in dem Baum gibt, dann ist die Gesamtzeit für das Zusammenführen $l\cdot cn$‍. Was ist also $l$‍? Wir beginnen mit Teilproblemen der Größe $n$‍ und halbieren immer wieder, bis wir zu Teilproblemen der Größe $1$‍ kommen. Wir haben diese Eigenschaft gesehen, als wir die binäre Suche analysiert haben, und die Antwort ist $l={\log }_{2}n+1$‍. Wenn zum Beispiel $n=8$‍, dann ist ${\log }_{2}n+1=4$‍, und sicher, der Baum hat vier Ebenen: $n=8,4,2,1$‍. Die Gesamtzeit für mergeSort ist also $cn({\log }_{2}n+1)$‍. Wenn wir die big-Θ Notation verwenden, um diese Laufzeit zu beschreiben, können wir den Term niedriger Ordnung ($+1$‍) und den konstanten Koeffizienten ($c$‍) verwerfen, was uns eine Laufzeit von $\mathrm{\Theta }(n{\log }_{2}n)$‍ gibt, wie versprochen.

Noch eine Sache über Merge Art ist bemerkenswert. Beim Kombinieren wird eine Kopie des gesamten zu sortierenden Arrays erzeugt, mit einem Teil der Daten in lowHalf und dem anderen Teil in highHalf. Mergesort benötigt also zusätzlichen Speicher für eine Kopie des gesamten Arrays wo die eigentliche Kombinations-Arbeit geschieht. Daher sagen wir, dass Mergesort nicht in-place funktioniert. Im Gegensatz dazu arbeiten sowohl Selectionsort als auch Insertionsort in-place, da sie niemals eine Kopie von mehr als einer konstanten Anzahl von Arrayelementen zu irgendeinem Zeitpunkt machen. Der zusätzliche Speicherbedarf ist also von der Größe des Arrays unabhängig. Informatiker wissen gern, wie ein Algorithmus arbeitet, denn es gibt einige Systeme (z.B. Embedded-Systeme), in denen Speicherplatz besonders knapp ist, und somit werden dort gerne in-place Algorithmen verwendet.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.