Queue <T> O (1) time

Question

Я только что создал методы enqueue, dequeue и 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

Ну, enqueue и dequeue запускаются в постоянное время, и заглядывает в линейное время.

Идея анализа сложности - это просто подсчет количества операций. Все, что нам нужно сделать, это предположить, что создание узла, присвоение значения и оценка оператора if выполняется в O (1).

Для ввода и удаления очереди, независимо от того, где выполняется код, существует постоянное количество этих операций. Таким образом, в итоге код просто выполняет постоянное число операций O (1), что дает сложность O (1).

Для метода peek код вводится в wile столько раз, сколько узлов в очереди. Так что, если есть n узлов, код вводится n раз цикл: он n O (1) операции. В конце: peek имеет линейную сложность.

Наличие метода печати всех значений очереди, выполняющей линейное время, на самом деле не имеет большого значения, поскольку оно включает итерацию через структуру.