java - 队列 O(1)时间

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

嗯，入队和出队以恒定时间运行，而 peek 以线性时间运行。

分析复杂性的想法只是计算操作的数量。我们所要做的就是假设创建一个节点、赋值并计算 if 语句的时间复杂度为 O(1)。

对于入队和出队，无论代码在哪里运行，这些操作的数量都是恒定的。所以最终，代码只执行了恒定数量的 O(1) 操作，这使得复杂性为 O(1)。

对于 peek 方法，代码进入队列的次数与队列中节点的数量相同。因此，如果有 n 个节点，代码将进入 n 次循环:它执行 n O(1) 次操作。最后:peek 具有线性复杂度。

让一个方法打印运行线性时间的队列的所有值实际上没什么大不了的，因为它涉及遍历结构。