各种数据结构的时间复杂度是多少？

我试图列出常见数据结构（如数组、二叉搜索树、堆、链表等）操作的时间复杂度，特别是我指的是 Java。它们很常见，但我想我们中的一些人对确切的答案并不是 100% 有信心。非常感谢任何帮助，尤其是参考资料。

例如。对于单链表：更改内部元素的时间复杂度为 O(1)。你怎么能这样做？你HAVE在更改元素之前搜索该元素。另外，对于 Vector，添加内部元素的时间复杂度为 O(n)。但为什么我们不能使用索引在摊余常数时间内完成呢？如果我遗漏了什么，请纠正我。

我将我的发现/猜测作为第一个答案发布。

Arrays

• 设置、检查特定索引处的元素：O(1)
• 搜寻中: O(n)如果数组未排序并且O(log n)如果数组已排序并且使用类似二分搜索的方法，
• 正如所指出的Aivean，没有Delete可以在数组上进行操作。我们可以通过将元素设置为某个特定值来象征性地删除它，例如-1、0等，取决于我们的要求
• 相似地，Insert对于数组来说基本上是Set正如开头提到的

数组列表：

• Add: 摊销 O(1)
• Remove: O(n)
• Contains: O(n)
• Size: O(1)

链接列表：

• 插入: O(1)，如果在头部完成，O(n)如果在其他地方，因为我们必须通过线性遍历链表来到达该位置。
• Deleting: O(1)，如果在头部完成，O(n)如果在其他地方，因为我们必须通过线性遍历链表来到达该位置。
• 搜寻中: O(n)

双向链表：

• 插入: O(1)，如果在头部或尾部进行，O(n)如果在其他地方，因为我们必须通过线性遍历链表来到达该位置。
• Deleting: O(1)，如果在头部或尾部进行，O(n)如果在其他地方，因为我们必须通过线性遍历链表来到达该位置。
• 搜寻中: O(n)

Stack:

• Push: O(1)
• Pop: O(1)
• Top: O(1)
• Search（类似于查找，作为一种特殊操作）：O(n)（大概吧）

队列/双端队列/循环队列：

• Insert: O(1)
• Remove: O(1)
• Size: O(1)

二叉搜索树：

• 插入、删除和搜索：平均情况：O(log n)， 最坏的情况下：O(n)

红黑树：

• 插入、删除和搜索：平均情况：O(log n)， 最坏的情况下：O(log n)

堆/优先级队列（最小/最大）：

• 求最小值/求最大值: O(1)
• Insert: O(log n)
• 删除最小值/删除最大值: O(log n)
• 提取最小/提取最大: O(log n)
• 查找、删除（如果提供的话）：O(n)，我们必须扫描所有元素，因为它们不像 BST 那样排序

哈希映射/哈希表/哈希集：

• 插入/删除: O(1)摊销的
• 调整大小/散列: O(n)
• Contains: O(1)