|
这个网页介绍了用于计算机科学的常见算法的空间和时间Big-O复杂度。过去我在准备技术岗位面试时，常常花好多时间从网上查找并归纳诸多搜索和排序算法在最佳情况、平均情况和最差情况下的复杂度，以便我在面试时不会被面试官问倒。最近这几年，我面试了硅谷的几家初创公司，还面试了一些规模更大的公司，比如谷歌、Facebook、雅虎、LinkedIn 和eBay。每次我为面试做准备，就问自己：“为什么没人制作一份简单明了的Big-O速查表呢？”于是，为了节省诸位读者的富贵时间，我就索性制作了一份速查表。希望你喜欢！
Big-O复杂度图表
常见的数据结构操作 数据结构 | 时间复杂度 | 空间复杂度 |
| 平均情况 | 最差情况 | 最差情况 |
| 访问 | 搜索 | 插入 | 删除 | 访问 | 搜索 | 插入 | 删除 |
| 数组 | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) | 堆栈 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) | 队列 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) | 单链表 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) | 双链表 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) | 跳跃表 | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | 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) | 二叉树 | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) | 笛卡尔树 | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) | B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | 红-黑树 | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | 伸展树 | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | AVL树 | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | KD树 | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
|
|
|
|
|
|
|
|
|
|
数组排序算法 算法 | 时间复杂度 | 空间复杂度 |
| 最佳情况 | 平均情况 | 最差情况 | 最差情况 | Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) | Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) | Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) | Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) | Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) | Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) | Bucket Sort | Ω(n k) | Θ(n k) | O(n^2) | O(n) | Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n k) | Counting Sort | Ω(n k) | Θ(n k) | O(n k) | O(k) | Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
|
