Warum ist Merge Sort Worst Case Laufzeit O (n log n)?

Den Merge-Sort verwenden Sie die Teile und herrsche " - Ansatz zur Lösung des Sortier-Problems. Erstens, es teilt sich den Eingang in die Hälfte mit Rekursion. Nach der Division, Sortieren Sie die Hälften und führen Sie Sie in eine sortierte Ausgabe. Siehe die Abbildung

Bedeutet dies, dass die besser zu Sortieren Hälfte von Ihrem problem und machen Sie einen einfachen merge eine Unterroutine. So ist es wichtig zu wissen, die Komplexität der merge eine Unterroutine, und wie oft es aufgerufen wird, in die Rekursion.

Den pseudo-code für die merge-sort ist wirklich einfach.

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

Es ist leicht zu sehen, dass in jeder Schleife, die Sie haben werden 4 Operationen: k++i++ oder j++die if-Anweisung und die attribution C = A|B. So haben Sie weniger oder gleich 4N + 2 Operationen geben einen O(N) Komplexität. Zum Wohle der Nachweis 4N + 2 werden so behandelt, 6N, da ist wahr für N = 1 (4N +2 <= 6N).

Also davon aus, dass Sie eine Eingabe mit N Elemente und übernehmen N ist eine Potenz von 2 ist. Auf jeder Ebene, haben Sie zwei mal mehr Teilprobleme, die mit einem Eingang mit der Hälfte der Elemente von der vorherigen Eingabe. Dies bedeutet, dass auf der Ebene j = 0, 1, 2, ..., lgN wird es 2^j Teilprobleme mit einer Eingabe der Länge N /2^j. Die Anzahl der Operationen auf jeder Ebene j wird weniger oder gleich

2^j * 6(N /2^j) = 6N

Beobachten, dass es doens egal, die Ebene, die Sie haben immer weniger oder gleich 6N Operationen.

Da gibt es lgN + 1 Ebenen, die Komplexität

O(6N * (lgN + 1)) = O(6N*lgN + 6N) = O(n lgN)

Referenzen:

• Coursera-Kurs Algorithmen: Entwurf und Analyse Teil 1

InformationsquelleAutor der Antwort Davi Sampaio

Nachdem die Aufteilung der Arrays auf die Bühne, wo man einzelne Elemente, d.h. nennen Sie Teillisten,

• in jeder Phase vergleichen wir die Elemente der jede Unterliste mit den angrenzenden Teilliste. Zum Beispiel, [die Wiederverwendung @Davi ' s Bild
  ]

  

  1. Auf Stufe-1 jedes element ist im Vergleich mit den angrenzenden, also n/2 Vergleiche.
  2. Auf die Bühne-2, jedes element von Teilliste ist im Vergleich mit den angrenzenden Teilliste, da jede Teilliste wird sortiert, dies bedeutet, dass die maximale Anzahl der Vergleiche zwischen zwei Teillisten ist <= Länge der Teilliste d.h. 2 (Stufe-2) und 4 vergleichen auf der Bühne-3 und 8 auf Stufe-4 da die Teillisten halten, die Verdoppelung der Länge. Was bedeutet, dass die maximale Anzahl der Vergleiche in jeder Phase = (Länge der Teilliste * (Anzahl der Teillisten/2)) ==> n/2
  3. Wie hast du Sie beobachtet die Gesamtzahl der Stufen wäre log(n) base 2
     Damit die gesamte Komplexität wäre == (max Anzahl der Vergleiche in jeder Phase * Anzahl der Stufen) == O((n/2)*log(n)) ==> O(nlog(n))

InformationsquelleAutor der Antwort blueskin

Viele der anderen Antworten sind toll, aber ich didn ' T sehen jede Erwähnung von Höhe und Tiefe im Zusammenhang mit der "merge-sort Baum" Beispiele. Hier ist ein weiterer Weg der Annäherung an die Frage mit einem großen Schwerpunkt auf den Baum. Hier ist noch ein Bild zur Erklärung:

Nur eine Zusammenfassung: wie andere Antworten haben darauf hingewiesen, wir wissen, dass die Arbeit der Zusammenführung von zwei sortierte Scheiben von der Sequenz in linearer Zeit (die Seriendruck-Funktion, die wir aufrufen, von der Haupt-Sortier-Funktion).

Jetzt suchen auf diesem Baum, wo wir uns vorstellen können, jeder Nachkomme der Wurzel (außer der Wurzel) einen rekursiven Aufruf der Sortier-Funktion, lassen Sie uns versuchen, zu beurteilen, wie viel Zeit verbringen wir auf jedem Knoten... Da das aufschneiden der Sequenz und Zusammenführen (beide zusammen) nehmen die lineare Zeit, die Zeit an jedem Knoten linear mit Bezug auf die Länge der Sequenz in diesem Knoten.

Hier ist, wo die Baum-Tiefe kommt. Wenn n die Gesamtgröße der ursprünglichen Sequenz, die Größe der Sequenz an einem beliebigen Knoten n/2ⁱwobei i die Tiefe. Dies ist gezeigt in der Abbildung oben. Putting dies zusammen mit der linearen Menge an Arbeit für jedes Segment haben wir eine Laufzeit von O(n/2ⁱ) für jeden Knoten in dem Baum. Jetzt müssen wir nur um die Summe, die für die n Knoten. Ein Weg dies zu tun ist, um das zu erkennen, es sind 2ⁱ - Knoten auf jeder Ebene der Tiefe in den Baum. So für alle level, wir haben O(2ⁱ * n/2ⁱ), O(n), denn wir können kündigen, die 2ⁱs! Wenn jeder Tiefe ist O(n), müssen wir nur multiplizieren, dass durch die Höhe dieser binäre Baum, der logn. Antwort: O(nlogn)

Referenz: Datenstrukturen und Algorithmen in Python

InformationsquelleAutor der Antwort trad

Die rekursive Struktur haben Tiefe log(N)und auf jeder Ebene in diesem Baum werden Sie tun, eine kombinierte N arbeiten zum Zusammenführen von zwei sortierten arrays.

Zusammenführen der sortierten arrays

Zum Zusammenführen von zwei sortierten arrays A[1,5] und B[3,4] Sie einfach Durchlaufen, sowohl am Anfang, sammeln der Unterste element zwischen den beiden arrays und Inkrementieren der Zeiger für das array. Sie sind fertig, wenn beide Zeiger bis zum Ende der jeweiligen arrays.

[1,5] [3,4]  --> []
 ^     ^

[1,5] [3,4]  --> [1]
   ^   ^

[1,5] [3,4]  --> [1,3]
   ^     ^

[1,5] [3,4]  --> [1,3,4]
   ^      x

[1,5] [3,4]  --> [1,3,4,5]
    x     x

Runtime = O(A + B)

Merge-sort Abbildung

Ihre rekursive Aufruf-stack wird wie folgt Aussehen. Die Arbeit beginnt an den unteren Blattknoten und Blasen.

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2

  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

Damit Sie N Arbeit an jedem k Ebenen in der Struktur, wo k = log(N)

N * k = N * log(N)

InformationsquelleAutor der Antwort geg