隊列<T> O（1）時間

Question

我剛剛創建了排隊，排隊和peek方法，但我不知道他們是否在O（1）時間。如果不是，我該怎麼做，並且你能解釋如何在O（1）時間內做到這一點嗎？

Node<T> start; 

public void enqueue(T val) 
{ 
    Node<T> n = new Node<T>(val); 

    if (start == null) 
    { 
     start = n; 
    } else 
    { 
     n.next = start; 
     start = n; 
    }  
} 
public T dequeue() 
{ 
    if (start != null) 
    { 
     T item = start.nodeValue; 
     start = start.next; 

     return item; 
    } 
    return null; 
} 


public void peek() 
{ 
    Node<T> curr = start; 
    while (curr != null) 
    { 
     System.out.print(curr.nodeValue + " "); 
     curr = curr.next; 
    } 
} 

Answer 1

它們位於O（1）或常量時間，因爲操作所花費的時間不受集合大小的影響。

Answer 2

好吧，入隊和出隊在恆定時間運行，並且在線性時間內運行。

分析複雜性的想法僅僅是計算操作的數量。我們所要做的就是假設創建一個節點，分配一個值並評估在O（1）中運行的if語句。

對於入隊和出隊，無論代碼在哪裏運行，都有一個固定數量的這些操作。所以最後，代碼只是做O（1）操作的常量，這給O（1）的複雜性。

對於peek方法，代碼輸入的次數與隊列中的節點數相同。因此，如果存在節點，則代碼輸入n次循環：它的確是n O（1）操作。最後：peek具有線性複雜性。

讓一個方法打印運行線性時間的隊列的所有值是沒有什麼大不了的，因爲它涉及遍歷結構。