数据结构和算法
描述
主要是在本站的文章中涉及到的一些数据结构
线性数据结构
非线性数据结构
算法性能速查表
| 常见数据结构 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 静态组 | 平均意义下 | 最坏情况 |
| 动态组 | 平均意义下 | 最坏情况 |
| 单/双链表 | 平均意义下 | 最坏情况 |
| 跳表 | 平均意义下 | 最坏情况 |
| 栈 | 平均意义下 | 最坏情况 |
| 队列 | 平均意义下 | 最坏情况 |
| 哈希表 | 平均意义下 | 最坏情况 |
| 二叉搜索树 | 平均意义下 | 最坏情况 |
| 自平衡的二叉搜索树 | 平均意义下 | 最坏情况 |
| 优先队列 | 平均意义下 | 最坏情况 |
| 字典树 (字符串的平均长度为 k) | 平均意义下 | 最坏情况 |
| KD树 | 平均意义下 | 最坏情况 |
| 常见操作 | 根据下标查找元素 | 根据数值查找下标 | 插入元素 | 删除元素 | 找最小/最大 | 根据下标查找元素 | 根据数值查找下标 | 插入元素 | 删除元素 | 找最小/最大 |
|---|---|---|---|---|---|---|---|---|---|---|
| 静态组 | O(1) | O(n) | - | - | O(n) | O(1) | O(n) | - | - | O(n) |
| 动态组 | O(1) | O(n) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| 单/双链表 | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 跳表 | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(log n) | O(log n) | O(n log n) |
| 栈 | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 队列 | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 哈希表 | - | O(1) | O(1) | O(1) | O(n) | - | O(n) | O(n) | O(n) | O(n) |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 自平衡的二叉搜索树 | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 优先队列 | - | O(n) | O(log n) | O(log n) | O(1) | - | O(n) | O(log n) | O(log n) | O(1) |
| 字典树 (字符串的平均长度为 k) | - | O(k) | O(k) | O(k) | O(nk) | - | O(nk) | O(nk) | O(nk) | O(nk) |
| KD树 | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
[i18n] feedback_title
[i18n] feedback_question
Glad to hear it! Please tell us how we can improve.
Sorry to hear that. Please tell us how we can improve.