| 数据结构 | 时间复杂度 | 空间复杂度 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 平均 | 最差 | 最差 | |||||||
| 访问 | 搜索 | 插入 | 删除 | 访问 | 搜索 | 插入 | 删除 | ||
| 数组 | Θ(1) | O(n) | O(n) | O(n) | Θ(1) | O(n) | O(n) | O(n) | O(n) |
| 堆栈 | O(n) | O(n) | Θ(1) | Θ(1) | O(n) | O(n) | Θ(1) | Θ(1) | O(n) |
| 队列 | O(n) | O(n) | Θ(1) | Θ(1) | O(n) | O(n) | Θ(1) | Θ(1) | O(n) |
| 单向链表 | O(n) | O(n) | Θ(1) | Θ(1) | O(n) | O(n) | Θ(1) | Θ(1) | O(n) |
| 双向链表 | O(n) | O(n) | Θ(1) | Θ(1) | O(n) | O(n) | Θ(1) | Θ(1) | O(n) |
| 跳跃表 | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| 哈希表 | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| 二叉搜索树 | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 笛卡尔树 | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| B树 | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(n) |
| 红黑树 | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(n) |
| 伸展树 | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | Θ(1) | Θ(1) | Θ(1) | O(n) |
| AVL树 | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(n) |
| KD树 | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(n) | O(n) | O(n) | O(n) | O(n) |
Log
Simple And Naive