Beste Antwort
Mergesort wird erstellt, wenn es zum Erstellen von Arrays in den rekursiven Aufrufen implementiert wird Viele von ihnen, aber sie existieren nicht gleichzeitig. Bei jedem rekursiven Aufruf erstellen Sie ein Array (oder 2, abhängig von einer Implementierung) zum Zusammenführen, und sie benötigen nicht mehr als O (n) Speicherplatz, und dann beim Zusammenführen Wenn dies erledigt ist, werden diese Arrays gelöscht und einige neue werden nach einem Moment in einem anderen rekursiven Aufruf erstellt. Wenn Sie gezählt haben, wie viel Speicherplatz alle jemals erstellten Arrays belegt haben, wäre dies „O (n log n)“. Sie müssen sich jedoch nicht um diese Informationen kümmern – Sie benötigen nicht mehr als O (n) Speicherplatz, da beim Erstellen eines Arrays alle anderen nicht mehr vorhanden sind und keinen Speicher belegen . Beachten Sie, dass Sie am Anfang einfach 2 – oder 3 – Arrays deklarieren können, jedes mit der Länge von n, und dann die Sequenz in einem von ihnen speichern können, während Sie das andere zum Zusammenführen verwenden, um die Leistung zu verbessern und Ihnen darüber hinaus zu zeigen Zweifel, es wird nicht mehr als O (n) Speicher benötigt.
Antwort
Beim Zusammenführen der Sortierung erstellen wir beim Zusammenführen des 2-sortierten Arrays 2 temporäre Arrays. L [ ] = Arr [links, Mitte] (linkes Array) zum temporären Speichern des alten Arrays von links nach Mitte (sortierte linke Hälfte) und R [] = Arr [Mitte + 1, rechts] (rechtes Array) zum temporären Speichern des alten Arrays Von Mitte + 1 nach rechts (sortierte rechte Hälfte) führen wir dann die beiden temporären Arrays mit dem ursprünglichen zusammen. Die Tatsache, dass wir zwei temporäre Arrays erstellen, um die Nummern des ursprünglichen Arrays zu speichern, da das ursprüngliche Array n Elemente enthält Arrays haben jeweils die Größe n und damit den zusätzlichen Raum von n und eine O (n) -Raumkomplexität. Der ursprüngliche Raum des Arrays wird bei der Berechnung der Raumkomplexität einer Sortierung nicht berücksichtigt Algorithmus.