Warum ist die Speicherkomplexität von Mergesort O (log (n)) mit verknüpften Listen?
Mergesort in einem Array hat die Speicherkomplexität O (n), während Mergesort in einer verknüpften Liste die dokumentierte Speicherkomplexität O (log (n)) hatHier
Ich glaube, dass ich den Array-Fall verstehe, weil wir beim Zusammenführen der beiden Sub-Arrays zusätzlichen Speicher benötigen. Aber würde eine Zusammenführungssortierung für verknüpfte Listen nicht einfach die beiden untergeordneten verknüpften Listen zusammenführen? Ich denke, dies hätte die Raumkomplexität O (1), um einen neuen Kopf zu erzeugen.
In Place Merge (kein Zusatzspeicher):
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;
}
Eine Erklärung wäre toll.