這個反向單鏈表算法的複雜性？

這個算法的複雜性是什麼？我假設它是O（N），但我想要一些澄清。如果我在鏈表中有一個尾部，我會認爲這會更快，因爲我完全避免讓while（current！= null）循環循環到列表的末尾。這個反向單鏈表算法的複雜性？

public void reverse() { 
    Stack<Node> stack = new Stack<Node>(); 
    if (this.head != null || this.head.next != null) { 
     Node current = this.head; 
     while (current != null) { 
      stack.push(current); 
      current = current.next; 
     } 
     Node last = null; 
     while (!stack.empty()) { 
      if (last==null) { 
       this.head = stack.pop(); 
       last = this.head; 
       continue; 
      } 
      last.next = stack.pop(); 
      last = last.next; 
      if (stack.empty()) { 
       last.next = null; 
      } 
     } 
    } 
}

來源

2012-08-16 volk

你應該問一個明確的問題，告訴我們你期望的答案。 – SDwarfs 2012-08-16 22:13:50

我重新編輯它，但基本上我問這個算法的運行時間複雜度是什麼 – volk 2012-08-16 22:15:06

是的，它是O（n * constant），它是O（n），假設java堆棧push和pop是O（1），恰好是這種情況。你的空間複雜度也是O（n），並且在空間複雜度O（1）中有辦法做到這一點。 – hatchet 2012-08-16 22:24:30

您是通過遍歷目錄，這是一種N推動所有鏈表元素到堆棧中，然後你遍歷棧，另外N，所以你在O指令符號（2N）

看到how to reverse a list with O(1) space and O(n) time?

來源

2012-08-16 22:15:21 ams

所以基本上是O（N） - 線性時間？ – volk 2012-08-16 22:18:53

如果我正確地記住了我的複雜性理論，那麼你可以放棄這個常數，所以你會認爲它是O（N） – ams 2012-08-16 22:24:08

該算法在類O（N）中。你使用N次操作的靜態數量（第一次循環），然後再次使用靜態數量的操作（第二次循環）; Stack.pop（）應該獨立於「N」;所以這意味着它在O（2N + c）類中，並且O（2N + c）在O（N）中的O（2N）類中。換句話說：例程的運行時間隨着堆棧中元素的數量而線性增加。

或簡單地說：是的，它在O（N）級。

來源

2012-08-16 22:24:57 SDwarfs

這個反向單鏈表算法的複雜性？

回答

相關問題