栈、队列、集合和双端队列的时间复杂度是什么？

Question

栈、队列、集合和双端队列在插入、搜索、索引、空间和删除复杂度方面的大O效率是什么？

我将为您解释一下它们各自的特点并简化了语言。

- cereallarceny

---

谢谢你的讽刺，@MikeDinescu。我已经在Google上搜索了将近一个小时，但并没有找到太多答案。我的研究并不局限于一种来源，请不要认为我没有尝试自己找到答案。 - cereallarceny

你具体发现了什么，有什么具体问题需要问吗？ - Mike Dinescu

我找到的关于这个问题的所有内容都与各种实现有关，但我找到的所有内容都没有讨论大O符号。事实上，我最信息丰富的来源是维基百科，它为这些数据类型提供了良好的入门介绍，但也没有解释它们的效率。 - cereallarceny

好的，我已经重新表述了我的问题，只用了一个简明扼要的句子。我省略了我尝试过和搜索过的内容，因为显然那会招来那些更注重自负而不是帮助别人理解难以理解概念的人的攻击。 - cereallarceny

Answer 1

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

让我们假设Stack类使用Node实现（也可以使用LinkedList、ArrayList、array等进行实现）。

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

栈有三种主要方法：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)的方法。它将搜索栈，以查看是否包含一个包含值等于v的Node。

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

基本上，我们会沿着节点引用移动，直到找到该值或到达末尾。在某些情况下，您可能会很早就发现该值，在某些情况下则更晚。然而，我们关心最坏情况！最坏的情况是我们必须检查每个单独的Node。假设有n个节点，那么我们的时间复杂度为O(n)。

您可以将这些分析技巧应用于其他数据结构，因此您可以自己解决其余部分。这并不太难。祝你好运。 :)

- But I'm Not A Wrapper Class

Answer 2

我一直在使用这个：http://bigocheatsheet.com/，但几乎没有关于为什么使用这些大O值的信息。你必须自己挖掘和研究。

- Saltymule

Answer 3

我很惊讶你在网上找不到这些信息。

问题中列出的数据结构有所区别。我将从队列和栈数据结构开始。堆栈和队列都提供专门的数据访问方式，因为没有随机访问，只有顺序访问。因此，您不能谈论随机访问性能。在这种情况下，任何堆栈或队列的良好实现都将提供O(1)访问，无论是插入还是删除操作（以其各自的形式）。

集合是一种非常不同的结构，其性能将严重依赖于底层实现。例如，您可以使用底层哈希表实现集合，以获得接近恒定时间的插入、删除和查找操作，或者您可以使用平衡搜索树来实现它，以获得O(log n)的时间复杂度。

- Mike Dinescu

---

在这个语境中，我认为 "dequeue" 指的是 "双端队列"，也就是在两个方向上都可以链接的队列。 - pm100

Answer 4

问题在于这些数据结构通常是基于其他数据结构实现的。例如，一个set可以被实现为哈希表或使用红黑树算法。

堆栈不提供随机访问，但通常被实现为一块内存（例如数组），其中一个元素指向更新为堆栈顶部的单个元素，用于push和pop操作。 queue可以被实现为具有非常不同插入、删除和索引特性的数组或链接列表。deque更可能被实现为链接列表，但C ++标准库中的Microsoft实现使用了混合方法（请参见What the heque is going on with the memory overhead of std::deque?）。

- Steve

Answer 5

大O符号通常用于算法和函数，而不是数据类型。
此外，时间复杂度非常取决于实现方式。询问“堆栈”数据类型的大O时间复杂度就像询问“排序”的大O时间复杂度一样。这完全取决于实现方式。（更具体地说，某些特定情况下的优化和要求可能会显著修改时间复杂度。）

如果您想使用C++ STL作为参考实现，可以从这里找到每个列出的数据类型的复杂度详细信息。只需搜索数据类型和操作即可。

- Mr. Llama