Requisitos de espacio de una ordenación por combinación
Estoy tratando de comprender los requisitos de espacio para Mergesort, O (n).
Veo que los requisitos de tiempo son básicamente, cantidad de niveles (logn) * fusión (n), por lo que eso 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
Ok, gracias a @Uri, este es el truco.
Lo que no pude ver al principio es que el tiempo solo suma, mientras que la memoria suma y resta, por lo que la cantidad máxima de tiempo es al final de la ejecución, pero la cantidad máxima de memoria está en la parte inferior de la pila recursiva.
Entonces, si seguimos sumando n + n/2 + n/4 + n/8.... no importa cuántas veces sumamos, nunca será mayor que 2n, y cuando lleguemos a la pila recursiva abajo y comenzamos a subir, no mantenemos la memoria utilizada para la rama anterior, por lo que, como máximo, 2n sería la cantidad de memoria utilizada, O(n).
Hay versiones de merge-sort que pueden funcionar en su lugar.
Sin embargo, en la mayoría de las implementaciones el espacio es lineal en el tamaño de la matriz. Eso significa n para el primer nivel, n/2 para el segundo, n/4 para el tercero, etc. Cuando llegue al final de su recursividad, esta serie suma aproximadamente 2n, que es lineal.
Esta es mi explicación de la complejidad espacial de su código. Básicamente, a medida que el algoritmo alcanza resultados, ¿cómo nos va con la memoria?
1) Cada llamada recursiva que realiza tiene un tamaño constante de marco de pila asignado, así como cualquier variable que no sea función de "n". Llamemos a esta constante "c". Dado que vas a niveles lg(n) profundos, el resultado es c*lg(n), que es O(lg(n)).
2) Ahora, mientras 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 las personas que se pregunten cómo se nos ocurrió n/(2^k), observen que primero asignamos memoria al resolver la primera mitad de la matriz, es decir, left=merge_sort(left). Una vez que finaliza este árbol de recursividad, terminamos desasignando toda la memoria y volvemos al punto de partida antes de resolver el lado derecho. Por lo tanto, es n/(2^k). Esto será O(n).
3) Finalmente, el procedimiento de fusión también puede asignar espacio adicional (si se utiliza una lista vinculada, es posible que este espacio no sea necesario), que es O(n)
Respuesta final = O(lg(n)) + O(n) + O(n) que es O(n).
