导入
速查表
这是各种数据结构和算法的最坏情况复杂度汇总。
数据结构
| 数据结构 | 最坏情况复杂度 | 说明 | ||||||
|---|---|---|---|---|---|---|---|---|
| 数组 |
| |||||||
| 链表 |
| 注意：若新元素始终插入链表头部，则插入操作的时间复杂度为 O(1)。 | ||||||
| 二叉树 |
| 在最坏情况下，二叉树可能退化为链表结构。 | ||||||
| 动态数组 |
| 此处的“访问”指的是通过数组特定索引进行访问。 | ||||||
| 栈 |
| 栈和队列通常不会涉及复杂的性能问题。这里列出它们是为了完整性。这两种数据结构更重要的是其“后进先出”（栈）和“先进先出”（队列）的特性。 | ||||||
| 队列 |
| |||||||
| 优先队列（二叉堆） |
| |||||||
| 哈希表 |
| 需注意，哈希表在平均情况下的插入和查找时间复杂度为 O(1)。 | ||||||
| B-树 |
| |||||||
| 红黑树 |
|
算法
| 类别 | 最坏情况复杂度 | 说明 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 排序 |
| 注意：尽管快速排序的最坏情况性能为 O(n²)，但由于其平均情况时间复杂度为 O(n log n)，因此在实际中仍被广泛使用。 | ||||||||||
| 树 |
| n 表示树中节点的总数。大多数树的遍历算法都需要访问每个节点，因此其最坏情况时间复杂度为 O(n)。 |