各种数据结构的时间复杂度是多少？ [英] What are the time complexities of various data structures?

问题描述

我正在尝试列出常用数据结构（如数组，二进制搜索树，堆，链接列表等）的操作时间复杂度，特别是我指的是Java。他们很常见，但我想我们中的一些人对于确切的答案并不满足100％的信心。非常感谢任何帮助，特别是参考文献。

I am trying to list time complexities of operations of common data structures like Arrays, Binary Search Tree, Heap, Linked List, etc. and especially I am referring to Java. They are very common, but I guess some of us are not 100% confident about the exact answer. Any help, especially references, is greatly appreciated.

例如。对于单链表：更改内部元素是O（1）。你怎么能这样做？您 HAVE 在更改元素之前搜索该元素。此外，对于Vector，将内部元素添加为O（n）。但是为什么我们不能使用索引在摊销的固定时间内做呢？如果我缺少某些东西，请更正我。

E.g. For singly linked list: Changing an internal element is O(1). How can you do it? You HAVE to search the element before changing it. Also, for the Vector, adding an internal element is given as O(n). But why can't we do it in amortized constant time using the index? Please correct me if I am missing something.

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

I am posting my findings/guesses as the first answer.

推荐答案

数组

• 设置，检查元素： O（1）


• 搜索： O n）如果数组未排序，并且 O（log n），如果数组被排序，并且使用类似二进制搜索的东西，


• 如所指出的通过 Aivean ，在数组上没有可用的删除操作。我们可以通过将元素设置为某个特定值来象征性地删除元素，例如-1，0等，取决于我们的要求


• 同样地，数组的插入基本上是 Set 如开头所述



Arrays

• Set, Check element at a particular index: O(1)
• Searching: O(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used,
• As pointed out by Aivean, there is no Delete operation available on Arrays. We can symbolically delete an element by setting it to some specific value, e.g. -1, 0, etc. depending on our requirements
• Similarly, Insert for arrays is basically Set as mentioned in the beginning


• 添加：分摊O（1）


• 删除 strong> O（n）


• 包含： O（n）


• 大小： O（1）


• Add: Amortized O(1)
• Remove: O(n)
• Contains: O(n)
• Size: O(1)


• 插入： O（1） O（n），因为我们必须通过线性链接链接表达到这个位置。


• 删除： O ），如果在头部， O（n），如果有其他地方，因为我们必须通过线性链接链接来达到这个位置。


• 搜索： O（n）


• Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Searching: O(n)


• 插入： O（1），如果在头部或尾部完成 O（n），如果其他任何地方，因为我们必须通过线性地链接链接来达到这个位置。 / li>
  
• 删除： O（1），如果在头部或尾部完成 O（n）
>

• Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Deleting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Searching: O(n)


• 推： O（1）


• 流行： O（1）


• 顶部： O（1）


• 搜索作为特殊操作）： O（n）（我猜是这样）


• Push: O(1)
• Pop: O(1)
• Top: O(1)
• Search (Something like lookup, as a special operation): O(n) (I guess so)


• 插入： O（1）


• 删除： O（1）


• 大小： O（1）


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


• 插入，删除和搜索：平均大小写： O（log n） / strong>，最差情况： O（n）


• Insert, delete and search: Average case: O(log n), Worst Case: O(n)


• 插入，删除和搜索：平均情况： O（日志n），最差情况： O（log n）


• Insert, delete and search: Average case: O(log n), Worst Case: O(log n)


• 查找最小/查找最大： O（1）


• 插入： O（日志n）


• 删除最小/删除最大： O （log n）


• 提取最小/提取最大值： O（log n）


• 查找，删除（如果提供）： O （n），我们将不得不扫描所有的元素，因为它们没有像BST一样排序


• Find Min/Find Max: O(1)
• Insert: O(log n)
• Delete Min/Delete Max: O(log n)
• Extract Min/Extract Max: O(log n)
• Lookup, Delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST


• 插入/删除： O（1）摊销


• Re-size / hash ： O（n）


• 包含： O（1）


• Insert/Delete: O(1) amortized
• Re-size/hash: O(n)
• Contains: O(1)

这篇关于各种数据结构的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！