数据结构-算法复杂度
数据结构 | 数据结构（英文名） | 时间复杂度 | 空间复杂度 | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
平均情况 | 最差情况 | 最差情况 | ||||||||
随机访问（Access） | 查询（Search） | 插入（Insertion） | 删除（Deletion） | 随机访问（Access） | 查询（Search） | 插入（Insertion） | 删除（Deletion） | |||
| 数组 | Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| 堆栈 | Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 队列 | Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 单链表 | Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 双链表 | Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 跳表 | Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| 哈希表 | Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| 二叉搜索树 | Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 笛卡尔树 | Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
| B树 | B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| 红黑树 | Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| 伸展树 | Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL树 | AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| KD树 | KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
相关概念：
稳定： 如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面
不稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 可能会出现在 b 的后面
时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
空间复杂度：指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数
推广