如何合并使用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：确保传统的mergesort是空间复杂度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 ） -list。

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）额外空间，您需要从递归的自上而下方法进行更改，在此方法中拆分列表分成两个大的子列表，对它们进行排序，并合并结果 - 给你一个Θ（log  n ）的递归深度 - 到迭代的自下而上方法你首先排序所有单例列表，然后是所有对（第一和第二元素，然后是第三和第四等），然后是所有四重奏（第一到第四个元素，然后是第五个到第八个，等等） - 给你Θ（log  n ）传递通过列表。每次传递都需要Θ（ 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:

• 节点合并（节点列表A，节点列表B），您已经写过。

节点mergePass（节点列表，int i）：

• 前提条件：节点＃1到＃ n 排序，节点＃（ n +1）到＃（2 n ）排序等。


• 后置条件：节点＃1到＃（2 n ）被排序，节点＃（2 +1）到＃（4 ）是排序等。


• 通过将节点＃1抓取到＃ n 并将节点＃（ n +1）抓取到＃（2 n ），切断它们，调用 merge ，然后粘贴结果;然后对节点＃（2 n +1）到＃（3 n ）和节点＃（3 n +1）执行相同的操作＃（4 名词的）;等等。

• 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.

节点mergeSort（节点列表）：

• 在其参数上调用 mergePass（...，1）。


• 在结果上调用 mergePass（...，2），然后调用 mergePass（...，4）在上结果等，每次加倍 i 。


• 停止之前 i 是列表的长度（或更大），因为 mergePass（...，i）是一个no-op if 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屋！