为什么mergesort空间复杂度O(log(n))与链表？

Question

数组上的Mergesort的空间复杂度为O(n),而链表上的mergesort的空间复杂度为O(log(n)),此处记录

我相信我了解数组的情况,因为在合并两个子数组时我们需要辅助存储.但是链接列表合并排序不会合并两个子链接列表到位吗？我认为这会产生空间复杂度O(1)来创建一个新头.

合并(无辅助存储):

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;
}

解释会很棒.

Answer 1

mergesort算法是递归的,因此对于数组和链表实例,它需要O(log n)堆栈空间.但是数组的情况下还分配了一个额外的O(n)空间,它占据了堆栈所需的O(log n)空间.所以数组版本是O(n),链表版本是O(log n).

Answer 2

Mergesort是一种递归算法.每个递归步骤都会在堆栈上放置另一个帧.排序64项将超过32项多一个递归步骤,它实际上是在堆栈的大小被称为当空间需求被认为是O(的log(n))来.