数组上的合并排序的空间复杂度为O（n），而链表上的合并排序的空间复杂度为O（log（n）），这在此处
Mergesort on an array has space complexity of O(n), while mergesort on a linked list has space complexity of O(log(n)), documented here
我相信我了解数组的情况，因为合并两个子数组时需要辅助存储。但是，链表合并合并不是仅将两个子链表合并到位吗？我认为这会产生创建新磁头的空间复杂度O（1）。
I believe that I understand the array case, because we need auxiliary storage when merging the two sub-arrays. But wouldn't a linked list merge sort just merge the two sub-linked lists in place? I think this would have space complexity O(1) for creating a new head.
就地合并（无辅助存储）：
In place merge (no auxiliary storage):
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; }一个解释会很好。
推荐答案Mergesort是一种递归算法。每个递归步骤都会在堆栈中放置另一个框架。对64个项目进行排序将比对32个项目进行更多的递归步骤，实际上，当说空间需求为O（log（n））时所引用的是堆栈的大小。
Mergesort is a recursive algorithm. Each recursive step puts another frame on the stack. Sorting 64 items will take one more recursive step than 32 items, and it is in fact the size of the stack that is referred to when the space requirement is said to be O(log(n)).
更多推荐
为什么带有链接列表的mergesort空间复杂度O（log（n））？
发布评论