Les besoins en espace d'une fusion de tri
J'essaie de comprendre les besoins d'espace pour un Mergesort, O(n).
Je vois que des exigences en gros, le nombre de niveaux(logn) * fusion(n) de sorte que (n log n).
Maintenant, nous sommes toujours à l'allocation de n par niveau, dans les 2 différents tableaux, de gauche et de droite.
Je ne comprends que la clé ici est que, lorsque les fonctions récursives de retour de l'espace devient libéré, mais je ne vois pas trop évident.
En outre, toutes les infos que j'ai trouver, seulement des états de l'espace requis est de O(n), mais ne l'explique pas.
Tout soupçon?
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
MODIFIER
Ok, merci à @Uri, c'est le truc
Ce que je n'ai pas réussi à voir au tout début, c'est que le temps n'ajoute que, alors que la mémoire ajoute et soustrait, de sorte que le montant maximum de temps à 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 de n + n/2 + n/4 + n/8.... il n'a pas d'importance combien de fois nous ajouter, ce ne sera jamais plus grand que 2n, et quand nous atteignons la pile récursive bas et commencer à monter, on ne garde pas la mémoire utilisée pour la branche précédents, donc au max, 2n serait la quantité de mémoire utilisée, O(n).
OriginalL'auteur Arkaitz Jimenez | 2010-06-03
Vous devez vous connecter pour publier un commentaire.
Il existe des versions de fusion sorte que l'on travail en place.
Cependant, dans la plupart des implémentations de l'espace est linéaire en la taille de la matrice. Cela signifie que n pour le premier niveau, n/2 pour le deuxième, n/4, pour le troisième, etc. Par le temps que vous êtes au fond de votre récursivité, cette série s'ajoute aux quelque 2n, ce qui est linéaire.
J'ai posté ce que je ne comprends maintenant, corrigez-moi si mal s'il vous plaît.
Vous êtes à la comprendre correctement. Le problème est avec le pseudo-code, Il est plus facile de visualiser le contrôle (et donc, le temps de la complexité) plutôt que sur le contenu de la pile d'appel.
Lorsque vous expliquez que la somme de (n, n/2, n/4,...) est responsable de la N de l'exécution, ne vous dites donc, avec une mise en œuvre de la fusion de tri qui crée un tableau à chaque fois que le cadre actuel des appels effectuer un tri sur un petits composant de tableau?
Si ce n'est pas vrai, ce qui signifie que le même tableau ont été transmis à trier, à chaque fois, ma compréhension est que la plus grande généraux, vous auriez est au sommet de la pile, lorsque l'on fusionne les deux moitiés du tableau original.
OriginalL'auteur Uri
C'est mon explication pour l'espace de la complexité de votre code. Fondamentalement, comme l'algorithme atteint des résultats comment en sommes-nous sur la mémoire.
1) Chaque récursion appel que vous faites a une taille constante de la pile allouée ainsi que toutes les variables qui ne sont pas d'une fonction de "n".
Appelons cette constanct "c". Depuis, vous allez lg(n) niveaux de profondeur, le résultat est c*lg(n) qui est O(lg n)).
2) Maintenant, comme nous l'calculer le résultat, nous allouer de l'espace à n/(2^k), où k est le niveau que vous.
Pour les gens qui demandez peut-être comment nous est venu à n/(2^k), notez que nous avons d'abord aller sur l'allocation de mémoire lors de la résolution de la première moitié du tableau, j'.e=gauche merge_sort(à gauche). Une fois, cette récursivité arbre est terminé, on finit par le libérer toute la mémoire et de revenir 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 plus d'espace trop (si vous utilisez la liste liée à cet espace peut ne pas être nécessaire) qui est O(n)
Réponse finale = O(lg n)) + O(n) + O(n), qui est en O(n).
OriginalL'auteur Frank Q.