Warteschlange <T> O (1) Zeit

Question

Ich habe gerade die Enqueue-, Dequeue- und Peek-Methoden erstellt, aber ich weiß nicht, ob sie in O (1) Zeit sind. Wenn nicht, wie kann ich das tun, und Können Sie mir erklären, wie man es in O (1) Zeit macht?

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

Sie sind in O (1) oder konstanter Zeit, weil die Zeit, die für die Operationen dauert nicht durch die Sammelgröße beeinflußt wird.

Answer 2

Nun, Enqueue und Dequeue laufen in konstanter Zeit und Peek läuft in linearer Zeit.

Die Idee für die Analyse der Komplexität ist lediglich die Anzahl der Operationen zu zählen. Alles, was wir tun müssen, ist davon auszugehen, dass ein Knoten erstellt, ein Wert zugewiesen und eine if-Anweisung in O (1) ausgewertet wird.

Für Enqueue und Dequeue gibt es eine konstante Anzahl dieser Operationen, egal wo der Code ausgeführt wird. Am Ende führt der Code nur eine konstante Anzahl von O (1) -Operationen durch, was O (1) -Komplexität ergibt.

Bei der Peek-Methode tritt der Code so oft in die Warteschlange ein, wie Knoten in der Warteschlange sind. Also, wenn es n Knoten gibt, gibt der Code n mal die Schleife: es tut n O (1) Operationen. Am Ende: Peek hat lineare Komplexität.

Mit einer Methode drucken alle Werte der Warteschlange läuft lineare Zeit ist wirklich keine große Sache, wie es durch die Struktur durchlaufen.