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

我试图列出常见的数据结构像数组，二叉search树，堆，链表等操作的时间复杂性，特别是我指的是Java。 他们是非常普遍的，但我想我们中的一些人并不是100％确切的答案。 任何帮助，特别是参考，非常感谢。

例如对于单链表：更改一个内部元素是O（1）。 你怎么能这样做？ 在更改元素之前，您必须先search元素。 此外，对于vector，添加一个内部元素给出为O（n）。 但是，为什么我们不能以分期固定的时间使用指数呢？ 请纠正我，如果我失去了一些东西。

我张贴我的发现/猜测作为第一个答案。

Answer 1

数组

• 设置，在特定索引处检查元素： O（1）
• search ： O（n）如果数组是未sorting的， O（log n）如果数组sorting并使用类似二进制search的东西，
• 正如Aivean指出的那样 ，数组中没有可用的Delete操作。 我们可以象征性地删除一个元素，将其设置为某个特定的值，例如-1,0等，这取决于我们的要求
• 同样，对于数组Insert基本上如前所述Set

数组列表：

• 加 ： 摊销的O（1）
• 删除 ： O（n）
• 包含 ： O（n）
• 尺寸 ： O（1）

链接列表：

• 插入 ： O（1） ，如果在头部完成，则O（n）在其他任何地方，因为我们必须线性移动链表到达该位置。
• 删除 ： O（1） ，如果在头部完成， O（n）是否在其他地方，因为我们必须线性地通过链表到达该位置。
• 搜寻 ： O（n）

双链表：

• 插入 ：如果在头部或尾部完成，则O（1） ， O（n）如果是其他地方，则由于我们必须线性移动链表来到达该位置。
• 删除 ： O（1） ，如果在头部或尾部完成，则O（n）在其他任何地方，因为我们必须线性移动链表到达该位置。
• 搜寻 ： O（n）

堆栈：

• 推 ： O（1）
• stream行音乐 ： O（1）
• 顶部 ： O（1）
• search （像查找，像一个特殊的操作）： O（n） （我猜是这样）

队列/ Deque /循环队列：

• 插入 ： O（1）
• 删除 ： O（1）
• 尺寸 ： O（1）

二进制search树：

• 插入，删除和search ：平均情况： O（log n） ，最差情况： O（n）

红黑树：

• 插入，删除和search ：平均情况： O（log n） ，最坏情况： O（log n）

堆/ PriorityQueue（最小/最大）：

• 查找最小值/查找最大值 ： O（1）
• 插入 ： O（log n）
• 删除最小值/删除最大值 ： O（log n）
• 提取最小/提取最大值 ： O（log n）
• 查找，删除 （如果有的话）： O（n） ，我们将不得不扫描所有的元素，因为它们没有像BST那样sorting

HashMap中/哈希表/ HashSet的：

• 插入/删除 ： O（1）摊销
• 重新大小/散列 ： O（n）
• 包含 ： O（1）