如何排序合并与O（nlogn）时间和O（1）空间复杂度

Question

链表（免责声明：学校）据我所知

，递归分割一个链表，然后发送它关闭另一个合并函数是O（nlogn）时间和O（n）空间。是否有可能在O（nlogn）时间和O（1）空间复杂度的链表上进行mergesort？你会如何去做这件事？

任何帮助表示赞赏

PS：确保传统归并为空间复杂度O（N），这是O（n）的一个例子，对不对？如何改变O（1）空间？

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

Answer 1

你的递归方法需要Θ（日志  ñ）额外的空间，因为你有Θ（日志  ñ）调用，当你一路下跌到merge-堆栈上排序单身人士名单。要将其减少到O（1）额外的空间，您需要从递归“自上而下”方法进行更改，在该方法中，将列表拆分为两个大的子列表，对它们进行排序并合并结果 - 给出你需要一个递归的深度为的Θ（日志  n） - 一个迭代的“自下而上”的方法，你首先排序所有的单例表，然后所有的对（第一和第二个元素，然后第三个和第四个等），然后所有四重奏（第一到第四个元素，然后是第五到第八等） - 给你Θ（日志  n）通过通过列表。每次通过取Θ（Ñ）时间，所以总时间仍然是Θ（Ñ  日志  Ñ）。

所以，总体来说，你有三种方法：

• Node merge(Node listA, Node listB)，你已经写。

• Node mergePass(Node list, int i)：

  • 前提：节点＃1至＃Ñ进行排序，节点＃（Ñ 1）到＃（2 Ñ）进行排序，等等
  • 后置条件：节点＃1到＃（2 ñ）进行排序，节点＃（2 ñ 1）到＃（4 ñ）进行排序，等等
  • 作品通过抓住节点＃1〜＃Ñ和节点＃（Ñ 1）到＃（2 Ñ）， “切割” 出来，主叫merge，以及 “粘贴” 中的结果;然后做同样为节点＃（2 Ñ 1）到＃（3 Ñ）和节点＃（3 Ñ 1）到＃（4 Ñ）;等等

• Node mergeSort(Node list)：

  • 电话mergePass(..., 1)在它的参数。
  • 调用mergePass(..., 2)的结果，然后调用mergePass(..., 4)对即结果等，每次加倍i。
  • 之前停止i是列表的长度（或更大），因为mergePass(..., i)是一个空操作，如果i是那么大。
  • 返回最后的结果。