Requisitos de espacio de merge-sort

Question

Estoy tratando de comprender los requisitos de espacio para un Mergesort, O (n).
Veo que los requisitos de tiempo son básicamente, la cantidad de niveles (logn) * merge (n) por lo que hace (n log n).
Ahora, todavía estamos asignando n por nivel, en 2 matrices diferentes, izquierda y derecha.
Entiendo que la clave aquí es que cuando las funciones recursivas regresan el espacio se desasigna, pero no lo veo demasiado obvio.
Además, toda la información que encuentro, solo indica que el espacio requerido es O (n) pero no lo explica.
¿Alguna pista?

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 

EDITAR Bien, gracias a @Uri, este es el truco
Lo que no ver al principio es que el tiempo sólo se suma, mientras que la memoria suma y resta, por lo que la cantidad máxima de el tiempo está al final de la ejecución, pero la cantidad máxima de memoria está en la parte inferior de la pila recursiva.

Por lo tanto, si seguimos agregando n + n/2 + n/4 + n/8 .... no importa cuántas veces agreguemos, nunca será mayor que 2n, y cuando Alcanzar el fondo recursivo de la pila y comenzar a subir, no guardamos la memoria utilizada para la rama anterior, por lo que al máximo, 2n sería la cantidad de memoria utilizada, O (n).

Answer 1

Existen versiones de merge-sort que pueden funcionar.

Sin embargo, en la mayoría de las implementaciones, el espacio es lineal en el tamaño de la matriz. Eso significa que n para el primer nivel, n/2 para el segundo, n/4 para el tercero, etc. Por el tiempo que están en la parte inferior de la recursividad, esta serie se eleva a aproximadamente 2n, que es lineal.

Answer 2

Esta es mi explicación de la complejidad del espacio para su código. Básicamente, a medida que el algoritmo alcanza resultados, ¿cómo nos va en la memoria?

1) Cada llamada de recursión que realice tiene un tamaño constante de marco de pila asignado, así como cualquier variable que no sea una función de "n". Llamemos a esto constante "c". Como, vas a niveles de LG (n) profundos, el resultado es c * lg (n) que es O (lg (n)).

2) Ahora, a medida que calculamos el resultado, asignamos espacio para n/(2^k) elementos, donde k es el nivel en el que se encuentra.

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

Para la gente que se estará preguntando cómo se nos ocurrió n/(2^k), aviso de que primero nos ocupamos de asignación de memoria en la resolución de la primera mitad de la matriz es decir izquierdo = merge_sort (izquierda). Una vez que este árbol de recursión finaliza, terminamos desasignando toda la memoria y volvemos al punto de partida antes de resolver para el lado derecho. Por lo tanto, es n/(2^k). Esto va a ser O (n).

3) Finalmente, fusionar procedimiento puede asignar espacio adicional también) (si se utiliza la lista puede no ser necesario este espacio) que es O (n)

respuesta final = O (lg (n vinculado) + O (n) + O (n) que es O (n).