各种数据结构的时间复杂性是什么？

Question

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

例如,对于单链表:更改内部元素是O(1).你怎么能这样做？你HAVE更改它之前要搜索的元素.另外,对于Vector,添加内部元素为O(n).但是为什么我们不能在使用索引的摊销常数时间内做到这一点？如果我错过了什么,请纠正我.

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

Answer 1

数组

• 设置,检查特定索引处的元素:O(1)
• 搜索:O(n)如果数组未排序,则O(log n)如果数组已排序并且使用类似二进制搜索的内容,
• 正如Aivean所指出的,Arrays上没有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)
• 流行:O(1)
• 上:O(1)
• 搜索(像查找一样的特殊操作):O(n)(我猜是这样的)

队列/ Deque /循环队列:

• 插入:O(1)
• 删除:O(1)
• 尺寸:O(1)

二叉搜索树:

• 插入,删除和搜索:平均情况:O(log n),最坏情况:O(n)

红黑树:

• 插入,删除和搜索:平均大小写:O(log n),最坏情况:O(log n)

堆/ PriorityQueue(最小/最大):

• 查找最小值/查找最大值:O(1)
• 插入:O(log n)
• 删除最小/删除最大值:O(log n)
• 提取最小/提取最大值:O(log n)
• 查找,删除(如果完全提供):O(n),我们将不得不扫描所有元素,因为它们没有像BST那样排序

HashMap中/哈希表/ HashSet的:

• 插入/删除:O(1)摊销
• 重新调整大小/哈希:O(n)
• 包含:O(1)