Platzbedarf eines Merge-sort

Question

Ich versuche, die Platzanforderungen für ein Mergesort, O (n) zu verstehen.
Ich sehe, dass Zeitanforderungen sind im Grunde, Menge an Ebenen (logn) * merge (n), so dass macht (n log n).
Jetzt vergeben wir noch n pro Ebene, in 2 verschiedenen Arrays, links und rechts.
Ich verstehe, dass der Schlüssel hier ist, dass, wenn die rekursiven Funktionen zurückkehren, der Raum freigegeben wird, aber ich sehe es nicht zu offensichtlich.
Darüber hinaus alle Informationen, die ich finde, nur Staaten benötigt Raum ist O (n), aber erkläre es nicht.
Irgendein Hinweis?

function merge_sort(m) 
    if length(m) ≤ 1 
     return m 
    var list left, right, result 
    var integer middle = length(m)/2 
    for each x in m up to middle 
     add x to left 
    for each x in m after middle 
     add x to right 
    left = merge_sort(left) 
    right = merge_sort(right) 
    result = merge(left, right) 
    return result 

EDIT Ok, dank @Uri, das ist der Trick
Was ich gleich am Anfang zu sehen, nur versäumt wird, dass die Zeit addiert, während der Speicher Additionen und Subtraktionen, so dass die maximale Menge an Die Zeit ist am Ende der Ausführung, aber die maximale Speichermenge befindet sich am unteren Ende des rekursiven Stacks.

Also, wenn wir hinzufügen, n + n/2 + n/4 + n/8 .... es spielt keine Rolle, wie oft wir hinzufügen, es wird nie größer als 2n, und wenn wir Erreichen Sie den rekursiven Stack-Bottom und fangen Sie an, nach oben zu gehen, wir behalten nicht den Speicher, der für den vorherigen Zweig verwendet wurde, also wäre 2n die Menge des verwendeten Speichers, O (n).

Answer 1

Es gibt Versionen von merge-sort, die funktionieren können.

In den meisten Implementierungen ist der Abstand jedoch linear in der Größe des Arrays. Das bedeutet n für die erste Ebene, n/2 für die zweite, n/4 für die dritte Ebene usw. Wenn Sie sich am Ende Ihrer Rekursion befinden, addiert sich diese Reihe zu etwa 2n, was linear ist.

Answer 2

Dies ist meine Erklärung für die Komplexität des Platzes für Ihren Code. Grundsätzlich, wie der Algorithmus Ergebnisse erreicht, wie geht es uns im Gedächtnis.

1) Jeder Rekursionsaufruf, den Sie vornehmen, hat eine konstante Größe des zugeordneten Stack-Frames sowie alle Variablen, die keine Funktion von "n" sind. Nennen wir diese Konstante "c". Da Sie lg (n) Ebenen tief gehen, ist das Ergebnis c * lg (n) was O (lg (n)) ist.

2) Nun, da wir das Ergebnis berechnen, ordnen wir Platz für n/(2^k) Elemente zu, wobei k die Ebene ist, auf der Sie sich befinden.

left = merge_sort(left) 
right = merge_sort(right) 

Für Leute, die sich fragen kann, wie wir mit n/(2^k) kam, bemerken, dass wir gehen über die Zuweisung von Speicher zuerst, wenn die erste Hälfte des Feldes zu lösen d.h = merge_sort (links) links. Sobald dieser Rekursionsbaum beendet ist, wird der gesamte Speicher freigegeben und wir kehren zum Ausgangspunkt zurück, bevor wir nach der rechten Seite suchen. Daher ist es n/(2^k). Dies wird O (n) sein.

3) Schließlich verschmelzen Verfahren zu zusätzlichen Platz zuweisen kann (wenn Liste verknüpft Verwendung dieser Raum nicht erforderlich), die O (n)

endgültige Antwort = O (lg (n)) + O (n) + O (n) welches O (n) ist.