Wymagania przestrzenne dotyczące scalania-sortowania

Question

Próbuję zrozumieć wymagania dotyczące miejsca dla Mergesorta, O (n).
Widzę, że wymagania czasowe są w zasadzie, ilość poziomów (logn) * scalenie (n) tak, że robi (n log n).
Teraz wciąż przydzielamy n na poziom, w 2 różnych tablicach, w lewo i w prawo.
Rozumiem, że kluczem jest to, że gdy funkcje rekursywne zwrócą, przestrzeń zostaje zwolniona, ale nie widzę tego zbyt oczywistego.
Poza tym, wszystkie informacje, które znajduję, tylko stany stanów wymagane są O (n), ale nie wyjaśniają tego.
Dowolna podpowiedź?

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, dzięki @Uri, jest to sztuczka
Co nie udało mi się zobaczyć na samym początku jest to czas tylko dodaje, podczas gdy pamięć dodaje i odejmuje, więc maksymalna kwota czas jest na końcu wykonywania, ale maksymalna ilość pamięci znajduje się na samym dole stosu rekursywnego.

Tak więc, jeśli nadal dodajemy n + n/2 + n/4 + n/8 ... nie ma znaczenia, ile razy dodamy, nigdy nie będzie większy niż 2n, a kiedy Sięgnij po dno rekursywnego dołu i zacznij iść w górę, nie przechowujmy pamięci używanej dla poprzedniej gałęzi, więc przy max. 2n będzie to ilość wykorzystanej pamięci, O (n).

Answer 1

Istnieją wersje sortowania korespondencji seryjnej, które mogą działać w miejscu.

Jednak w większości implementacji przestrzeń jest liniowa w rozmiarze tablicy. Oznacza to n dla pierwszego poziomu, n/2 dla drugiego, n/4 trzeciego itd. Do czasu, gdy jesteś na samym dole rekurencji, ta seria dodaje do około 2n, która jest liniowa.

Answer 2

To jest moje wyjaśnienie złożoności przestrzeni dla twojego kodu. Zasadniczo, gdy algorytm osiąga wyniki, jak robimy w pamięci.

1) Każde wywołanie rekursji ma stały rozmiar przydzielonej ramki stosu oraz dowolne zmienne, które nie są funkcją "n". Nazwijmy to konwencją "c". Ponieważ przechodzisz na głębokości lg (n), wynikiem jest c * lg (n), czyli O (lg (n)).

2) Teraz, obliczając wynik, przydzielamy przestrzeń dla elementów n/(2^k), gdzie k jest poziomem, na którym się znajdujesz.

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

Dla ludzi, którzy mogą się zastanawiać, jak wpadliśmy n/(2^k) należy zauważyć, że najpierw pójdziemy na temat pamięci przydziale przy rozwiązywaniu pierwszą połowę tablicy tj lewo = merge_sort (z lewej). Kiedy to drzewo rekurencji zostanie zakończone, kończymy przydzielanie całej pamięci i wracamy do punktu początkowego, zanim rozwiążemy prawą stronę. Stąd jego n/(2^k). To będzie O (n).

3) W końcu procedury scalania może przydzielić większą powierzchnią zbyt) (w przypadku korzystania lista może być niezbędny, przestrzeń), co O (N)

końcowa odpowiedź = O (lg (n związany) + O (n) + O (n), który jest O (n).