为什么带有链接列表的mergesort空间复杂度O（log（n））？ [英] Why is mergesort space complexity O(log(n)) with linked lists?

问题描述

数组上的合并排序的空间复杂度为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））？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！