stack - 堆栈、队列、集合和双端队列的 Big-O 是什么？

Question

与插入、搜索、索引、空间和删除复杂性相关的堆栈、队列、集合和双端队列的 Big-O 效率是多少？

Answer 1

这实际上取决于每个数据结构的实现。我将讨论一些，以便您了解如何确定这一点。

让我们假设 Stack 类是使用 Node 实现的(它也可以用 LinkedList 、 ArrayList 、 arrray 等来实现)。

Node top, bottom;
public Stack(Node n){
    top = bottom = n;
}

Stack 有 3 个主要方法:peek , push , 和 pop .

public int peek(){
    return top.value; //only return value
}

没有涉及太多处理。它只是返回一个原始值。这是 O(1) 对于时间和空间。

public void push(Node n){
    n.next = top;
    top = n;
}

仍然没有真正的处理。这是 O(1) 对于时间和空间。让我们跳过 pop()并尝试更有趣的事情。让我们尝试一个名为 contains(int v) 的方法.它将搜索堆栈以查看它是否包含 Node其中包含一个等于 v 的值.

public bool contains(int v){
    Node current = top;
    while(current != null){
        if(current.value == v){
            return true;
        }
        current = current.next;
    }
    return false;
}

基本上，我们将遍历 Node 引用，直到找到值或到达终点。在某些情况下，您会在早期发现值(value)，而在某些情况下，您会发现值(value)。但是，我们关心最坏的情况!最糟糕的情况是我们必须检查每一个 Node .说有 节点，那么我们有 O(n) .

你可以将这些分析技巧应用到其他数据结构上，剩下的就可以自己解决了。还不错。祝你好运。 :)