Pourquoi la complexité de l'espace de fusion est-elle O (log (n)) avec les listes liées?
Mergesort sur un tableau a de l'espace complexité de O(n), tandis que mergesort sur une liste liée a l'espace complexité de O(log(n)), documenté ici
Je crois que je comprends le tableau cas, car nous avons besoin d'auxiliaire de stockage lors de la fusion de deux sous-tableaux. Mais n'est-ce pas lié liste de fusion tri viens de fusionner les deux sous-listes liées à la place? Je pense que cela aurait de l'espace de complexité O(1) pour la création d'un nouveau chef.
En place de fusion (pas de mémoire auxiliaire):
public Node merge(Node a, Node b) {
Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
while(a !=null && b!= null) {
if(a.info <= b.info) { curr.next = a; a = a.next; }
else { curr.next = b; b = b.next; }
curr = curr.next;
}
curr.next = (a == null) ? b : a;
return dummyHead.next;
}
Une explication serait génial.
source d'informationauteur modulitos
Vous devez vous connecter pour publier un commentaire.
Mergesort est un algorithme récursif. Chaque étape récursive met une autre image sur la pile. Tri 64 éléments fera une de plus récursive étape de 32 éléments, et c'est en fait la taille de la pile qui est appelée lorsque l'espace est dit être en O(log(n)).
La mergesort algorithme est récursif, donc il faut O(log n) l'espace de pile, pour le tableau et la liste chaînée des cas. Mais le tableau cas alloue également un supplément de O(n) de l'espace, qui domine le O(log n) espace requis pour la pile. Ainsi, le tableau version est O(n), et la liste liée version est O(log n).