Espace requis pour un tri par fusion

Question

J'essaie de comprendre l'espace requis pour un Mergesort, O (n).
Je vois que les exigences de temps sont essentiellement, quantité de niveaux (logn) * fusionner (n) de sorte que fait (n log n).
Maintenant, nous allouons toujours n par niveau, dans 2 tableaux différents, à gauche et à droite.
Je comprends que la clé ici est que lorsque les fonctions récursives retournent l'espace est désalloué, mais je ne le vois pas trop évident.
En outre, toutes les informations que je trouve, seulement l'espace requis est O (n), mais ne l'expliquent pas.
Un conseil?

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, merci à @Uri, c'est le truc
Ce que je ne voyais pas au début est que le temps ne fait qu'ajouter, tandis que la mémoire ajoute et soustractions, de sorte que le montant maximum de le temps est à la fin de l'exécution, mais la quantité maximale de mémoire est au bas de la pile récursive. Donc, si nous continuons à ajouter n + n/2 + n/4 + n/8 ... peu importe combien de fois nous ajoutons, ce ne sera jamais plus grand que 2n, et quand nous atteindre le fond de la pile récursive et commencer à monter, nous ne conservons pas la mémoire utilisée pour la branche précédente, donc au maximum, 2n serait la quantité de mémoire utilisée, O (n).

Answer 1

Il existe des versions de tri de fusion qui peuvent fonctionner.

Cependant, dans la plupart des implémentations, l'espace est linéaire dans la taille de la matrice. Cela signifie n pour le premier niveau, n/2 pour le second, n/4 pour le troisième, etc. Au moment où vous êtes au bas de votre récurrence, cette série s'élève à environ 2n, ce qui est linéaire.

Answer 2

Ceci est mon explication de la complexité de l'espace pour votre code. Fondamentalement, comme l'algorithme atteint des résultats, comment allons-nous sur la mémoire.

1) Chaque appel de récursion que vous faites a une taille constante de trame de pile allouée ainsi que toutes les variables qui ne sont pas une fonction de "n". Appelons cela constanct "c". Puisque, vous allez en lg (n) niveaux profonds, le résultat est c * lg (n) qui est O (lg (n)). 2) Maintenant, comme nous calculons le résultat, nous allouons de l'espace pour les éléments n/(2^k), où k est le niveau auquel vous êtes.

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

Pour les gens qui peuvent se demander comment nous sommes arrivés avec n/(2^k), notez que d'abord nous faire au sujet de l'allocation de mémoire lors de la résolution de la première moitié du tableau i.e. gauche = merge_sort (à gauche). Une fois que cet arbre de récurrence est terminé, nous finissons par désallouer toute la mémoire et revenons au point de départ avant de résoudre pour le côté droit. Par conséquent, son n/(2^k). Cela va être O (n).

3) Enfin, la procédure de fusion peut allouer de l'espace supplémentaire trop (si vous utilisez liste chaînée cet espace ne peut pas être nécessaire) qui est O (n)

réponse finale = O (lg (n)) + O (n) + O (n) qui est O (n).