对于最常见的数据结构（包括数组、链表、哈希表等）的操作，没有可用的大 O 表示法的总结。
JCS
问问题
147920 次
6 回答
78
现在可以在 Wikipedia 上找到有关此主题的信息：搜索数据结构
+----------------------+----------+------------+----------+--------------+
| | 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.
于 2013-07-01T17:12:59.870 回答
16
我想我将从链表的时间复杂度开始：
Indexing---->O(n)
Inserting / Delete at end---->O(1) or O(n)
Inserting / Delete in middle--->O(1) with iterator O(n) with out
最后插入的时间复杂度取决于你是否有最后一个节点的位置，如果你有，那将是 O(1) 否则你将不得不搜索链表，时间复杂度会跳到 O (n)。
于 2008-09-23T18:37:53.637 回答
4
请记住，除非您正在编写自己的数据结构（例如 C 中的链表），否则它可能很大程度上取决于您选择的语言/框架中数据结构的实现。例如，在 Ridiculous Fish 上查看 Apple CFArray 的基准测试。在这种情况下，数据类型（来自 Apple 的 CoreFoundation 框架的 CFArray）实际上会根据数组中实际存在的对象数量来改变数据结构——从线性时间变为恒定时间（大约 30,000 个对象）。
这实际上是面向对象编程的美妙之处之一——您不需要知道它是如何工作的，只需知道它是如何工作的，并且“它是如何工作的”可以根据需求而改变。
于 2008-09-24T22:22:09.890 回答
4
红黑树：
- 插入 - O(log n)
- 检索 - O(log n)
- 删除 - O(log n)
于 2008-09-23T21:04:18.777 回答
3
没有比这更有用的了：通用数据结构操作：
于 2018-09-17T08:41:04.853 回答
1
哈希表的摊销 Big-O：
- 插入 - O(1)
- 检索 - O(1)
- 删除 - O(1)
请注意，散列算法有一个常数因子，摊销意味着实际测量的性能可能会有很大差异。
于 2008-09-23T21:01:11.013 回答