为什么链表的归并排序空间复杂度为 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)).

这篇关于为什么链表的归并排序空间复杂度为 O(log(n))?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！