Die merge-Funktion läuft in Θ(n) \Theta (n) Zeit, wenn sie n n Elemente kombiniert. Wie kann man zeigen, dass mergeSort in Θ(nlgn) \Theta (n \lg n) Zeit läuft ? Wir fangen an, über die drei Teile der Teile-und-Herrsche Strategie nachzudenken und wie wir ihre Laufzeiten bestimmen. Wir gehen davon aus, dass wir insgesamt n n Elemente im gesamten Array sortieren.
  1. Im Teile-Schritt wird der Mittelpunkt q q der Indizes p p und r r berechnet. Die Laufzeit ist damit unabhängig von der Subarray-Größe und dauert immer eine konstante Zeit. Zur Erinnerung: In der Big-Θ Notation geben wir konstante Zeit als Θ(1) \Theta (1) an.
  2. Der Herrsche-Schritt, wo rekursiv zwei Subarrays von jeweils etwa n/2 n/2 Elementen sortiert werden, dauert etwas, aber wir werden uns das gleich genauer anschauen, wenn wir die Unterprobleme betrachten.
  3. Im Kombinations-Schritt werden insgesamt n n Elemente kombiniert. Diese Dauer können wir mit Θ(n) \Theta (n) angeben.
Betrachten wir die Teile- und Kombinations-Schritte gemeinsam: Die Θ(1) \Theta (1) Laufzeit für den Teile-Schritt ist vernachlässigbar klein im Vergleich zur Θ(n) \Theta (n) Laufzeit des Kombinations-Schritts . Also können wir die Größenordnung der gemeinsamen Laufzeit der beiden Schritte mit Θ(n) \Theta (n) angeben. Um etwas konkreter zu werden sagen wir, dass der Teile- und Kombinations-Schritt zusammen cn cn Zeit in Anspruch nehmen, wobei c c eine Konstante ist.
Zur Vereinfachung gehen wir davon aus, dass wenn n>1 n>1 ist, dann ist n n immer gerade, also n/2 n/2 ist eine Ganzzahl. (Der Fall, in dem n n ungerade ist, ändert nicht das Ergebnis der Betrachtung in Bezug auf die Big-Θ Notation.) Damit ist die Laufzeit von mergeSort auf einem n n -Elemente Subarray das Doppelte der Laufzeit von mergeSort auf einem (n/2) (n / 2) -Elemente Subarray (für den Eroberungsschritt) plus cn cn (für die Teile- und Kombinations-Schritte).
Jetzt müssen wir die Laufzeit der beiden rekursiven Anrufe auf n/2 n/2 Elemente bestimmen. Jeder dieser beiden rekursiven Anrufe dauert doppelt solange wie die Laufzeit von mergeSort auf einem (n/4) (n/4) -Elemente Subarray (weil wir n/2 n/2 halbieren müssen) plus cn/2 cn/2 zum Zusammenführen. Wir haben zwei Teilprobleme der Größe n/2 n/2 , und jedes dauert cn/2 cn/2 Zeit zum Kombinieren, und so ist die benötigte Gesamtzeit zum Kombinieren der Teilprobleme der Größe n/2 n/2 gleich 2cn/2=cn 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 nn gekennzeichnet, also der Größe des Subarrays für das ursprüngliche n n -Elemente Array. Unterhalb der Wurzel sind zwei Kinder-Knoten, die jeweils mit n/2n/2 markiert sind, um die Größen des Subarrays für die beiden Teilprobleme der Größe n/2n/2 darzustellen.
Jedes der Teilprobleme der Größe n/2 n / 2 sortiert rekursiv zwei Subarrays der Größe (n/2)/2 (n/2)/ 2 oder n/4 n/4 . Weil es zwei Teilprobleme der Größe n/2 n/2 gibt, gibt es vier Teilprobleme der Größe n/4 n/4 . Jedes dieser vier Teilprobleme kombiniert insgesamt n/4 n/4 Elemente, und so ist die Kombinations-Zeit für jedes der vier Teilprobleme cn/4 cn/4 . Zusammengefasst über die vier Teilprobleme sehen wir, dass die gesamte Kombinations-Zeit für alle Teilprobleme der Größe n/4 n/4 gleich 4cn/4=cn 4\cdot cn/4 = cn ist:
Wie geht das wohl für die Teilprobleme der Größe n/8 n/8 weiter? Es wird acht von ihnen geben. Die Kombinations-Zeit für jedes Teilproblem wird cn/8 cn/8 sein, für eine Gesamt-Kombinations-Zeit von 8cn/8=cn 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 cncn. Irgendwann erreichen wir Unterprobleme der Größe 1: Dem Basisfall. Wir müssen dann Θ(1)\Theta (1) Zeit verwenden, um Subarrays der Größe 1 zu sortieren, denn wir müssen testen, ob p<rp<r ist, und dieser Test benötigt konstante Zeit. Wie viele Subarrays der Größe 1 gibt es? Da wir mit nn Elementen begonnen haben, muss es nn von ihnen geben. Da jeder Basisfall Θ(1)\Theta(1) Zeit dauert, nehmen die Basisfälle insgesamt cncn Zeit in Anspruch:
Jetzt wissen wir, wie lange die Kombination für jede Teilproblem-Größe dauert. Die Gesamtzeit für mergeSort ist die Summe der Kombinations-Zeiten für alle Ebenen. Wenn es l l Ebenen im Baum gibt, dann ist die Gesamt-Kombinations-Zeit cnl cn \cdot l . Wie bestimmen wir den Wert von l l ? Wir beginnen mit Teilproblemen der Größe n n und halbieren wiederholt bis wir auf Unterprobleme der Größe 1 stoßen. Wir haben diese Eigenschaft kennengelernt, als wir die Binärsuche analysierten, und die Antwort lautet l=lgn+1 l = \lg n + 1 . Zum Beispiel, wenn n=8 n = 8 ist, dann ist l=lg8+1=4 l=\lg 8 + 1 = 4 . Der Baum hat also vier Ebenen: n=8,4,2,1 n = 8, 4, 2, 1 . Die Gesamtzeit für mergeSort ist also cn(lgn+1) cn (\lg n + 1) . Wenn wir die Big-Θ Notation verwenden, um diese Laufzeit zu beschreiben, können wir den niederwertigen Term (+1 +1 ) und den konstanten Koeffizienten (c c ) verwerfen, was zu einer Gesamtlaufzeit von Θ(nlgn) \Theta (n \lg n) führt.
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.
Lade