如何排序合併與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是那麼大。
  • 返回最後的結果。