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

我试图列出常见数据结构操作的时间复杂性，如数组、二叉查找树、堆、链表等，特别是我指的是 Java。它们非常普遍，但是我想我们中的一些人对于确切的答案并没有100% 的信心。任何帮助，尤其是推荐信，我们都非常感激。

例如，对于单链表: 更改一个内部元素是 O (1)。你怎么能这么做？在更改元素之前，请使用 有搜索该元素。另外，对于 Vector，添加一个内部元素给定为 O (n)。但是为什么我们不能用指数在固定时间内分期付款呢？如果我遗漏了什么，请纠正我。

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

154065 次浏览
小开
最佳答案

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

ArrayList:

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

Linked List:

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

Doubly-Linked List:

  • Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traversing 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 traversing the linkedlist linearly.
  • Searching: O(n)

Stack:

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

Queue/Deque/Circular Queue:

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

Binary Search Tree:

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

Red-Black Tree:

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

Heap/PriorityQueue (min/max):

  • 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

HashMap/Hashtable/HashSet:

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

Baeldung pointed out some time complexities for the ArrayList, LinkedList, and CopyOnWriteArrayList here: https://www.baeldung.com/java-collections-complexity and for Map implementations here: https://www.baeldung.com/java-hashmap

He also added benchmarks to highlight differences among the implementations.


提交答案