如何合并排序具有 O(nlogn) 时间和 O(1) 空间复杂度的链表 [英] How to Merge sort a Linked List with O(nlogn) time and O(1) space complexity

问题描述

(免责声明:学校)

据我所知，递归拆分链表，然后将其发送到另一个函数进行合并是 O(nlogn) 时间和 O(n) 空间.是否可以在 O(nlogn) 时间和 O(1) 空间复杂度的链表上进行归并排序?你会怎么做?

As far as I know, recursively splitting a linked list, then sending it off to another function to merge is O(nlogn) time and O(n) space. Is it possible to do mergesort on linked list with O(nlogn) time and O(1) space complexity? How would you go about doing this?

感谢任何帮助

PS:为了确保传统归并排序是空间复杂度0(n)，这是0(n)的一个例子，对吧?O(1) 空间将如何更改?

PS: to make sure that the traditional mergesort is space complexity 0(n), this is an example of 0(n), right? How would it be changed for O(1) space?

void sortTrack() { 
    Node merge = this.head;
    this.head = Node (merge);
}

public Node mergeSort(Node head){
    if ((head == null)||(head.next == null)){
        return head;
    }
    Node left = head;
    Node right = head.next;
    while((right != null) && right.next != null){
        head = head.next;
        right = right.next.next;
    }
    right = head.next;
    head.next = null;
    return merge(mergeSort(left), mergeSort(right));
}

public Node merge(Node left, Node right){
    Node head = new Node ();
    Node temp = head;
    while((left != null) && (right !=null)){
        if(left <= right ){
            temp.next = left;
            temp = left;
            left = left.next;
        }
        else{
            temp.next = right;
            temp = right; 
            right = right.next;
        }
    }
    if(right == null)
        temp.next = left;
    else
        temp.next = right;
    return head.next;
}  

推荐答案

您的递归方法需要 Θ(log n) 额外空间，因为您将有 Θ(log n) 调用堆栈，当您一直向下合并排序单例列表时.

Your recursive approach requires Θ(log n) extra space, since you'll have Θ(log n) calls on the stack when you're all the way down to merge-sorting a singleton-list.

要将其减少到 O(1) 额外空间，您需要从递归的自上而下"方法更改，将列表拆分为两个大子列表，对它们进行排序，然后合并结果 — 为您提供Θ(logn) 的递归深度——迭代自底向上"方法，首先对所有单例列表进行排序，然后对所有对(第一个和第二个元素，然后是第三个和第四个，等等)，然后是所有的四重奏(第一个到第四个元素，然后是第五个到第八个，等等)——给你 Θ(logn) 通过列表.每次通过需要 Θ(n) 时间，所以总时间仍然是 Θ(n log n).

To reduce it to O(1) extra space, you'll need to change from a recursive "top-down" approach, where you split the list into two large sublists, sort them, and merge the results — giving you a recursive depth of Θ(log n) — to an iterative "bottom-up" approach where you first sort all the singleton-lists, then all the pairs (the first and second elements, then the third and fourth, etc.), then all the quartets (the first through fourth elements, then the fifth through eighth, etc.) — giving you Θ(log n) passes through the list. Each pass takes Θ(n) time, so the total time is still Θ(n log n).

总的来说，您将拥有三种方法:

So overall, you'll have three methods:

• Node merge(Node listA, Node listB)，你已经写好了.

Node mergePass(Node list, int i):

• 前提:节点#1到#n已排序，节点#(n+1)到#(2n)已排序等
• 后置条件:节点#1到#(2n)被排序，节点#(2n+1)到#(4n)>) 排序等
• 通过抓取节点 #1 到 #n 和节点 #(n+1) 到 #(2n) 来工作，切割" 他们出来，调用 merge，并将结果粘贴"进去；然后对节点 #(2n+1) 到 #(3n) 和节点 #(3n+1) 执行相同的操作#(4n);等

• precondition: nodes #1 to #n are sorted, nodes #(n+1) to #(2n) are sorted, etc.
• postcondition: nodes #1 to #(2n) are sorted, nodes #(2n+1) to #(4n) are sorted, etc.
• works by grabbing nodes #1 to #n and nodes #(n+1) to #(2n), "cutting" them out, calling merge, and "pasting" the result in; then doing the same for nodes #(2n+1) to #(3n) and nodes #(3n+1) to #(4n); etc.

Node mergeSort(Node list):

• 对其参数调用 mergePass(..., 1).
• 对结果调用mergePass(..., 2)，然后对那个结果调用mergePass(..., 4)等，每次都将 i 加倍.
• stops before i 是列表的长度(或更大)，因为 mergePass(..., i) 如果 i 是空操作 就是那么大.
• 返回最后的结果.

• calls mergePass(..., 1) on its argument.
• calls mergePass(..., 2) on the result, then calls mergePass(..., 4) on that result, etc., doubling i each time.
• stops before i is the length of the list (or bigger), since mergePass(..., i) is a no-op if i is that big.
• returns the last result.

这篇关于如何合并排序具有 O(nlogn) 时间和 O(1) 空间复杂度的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！