索引、插入和删除常见数据结构的时间复杂度是多少?

问题描述

对于最常见的数据结构(包括数组、链表、哈希表等)的操作，没有可用的大 O 表示法的摘要.

There is no summary available of the big O notation for operations on the most common data structures including arrays, linked lists, hash tables etc.

推荐答案

关于这个主题的信息现在可以在维基百科上找到:搜索数据结构

Information on this topic is now available on Wikipedia at: Search data structure

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list
   (i.e. if you have an iterator to the location) is O(1). If you don't
   know the location, then you need to traverse the list to the location
   of deletion/insertion, which takes O(n) time.

** The deletion cost is O(log n) for the minimum or maximum, O(n) for an
   arbitrary element.

这篇关于索引、插入和删除常见数据结构的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！