嗨，您好！该网页涵盖了计算机科学中常用算法的时空Big-O复杂性。过去在准备技术面试时，我发现自己花了数小时在互联网上搜寻和整理搜索算法和排序算法的最佳，平均和最坏情况，以免被问到这些问题时感到困惑。在过去的几年中，我采访了多家硅谷初创公司以及一些较大的公司，例如Google，Facebook，Yahoo，LinkedIn和Uber，每次我准备接受采访时，我都在想：有人创造了不错的Big-O备忘单吗？”。因此，为了节省大家很多时间，我创建了一个。请享用！-埃里克
复杂度通常会使用大-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-数 | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(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) |
数组排序算法
| 算法 | 时间复杂度 | 空间复杂度 | ||
|---|---|---|---|---|
| 最优 | 平均 | 最差 | 最差 | |
| 快速排序 | Ω(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) |
| 归并排序 | Ω(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Timsort | Ω(n) | O(n log(n)) | O(n log(n)) | O(n) |
| 堆排序 | Ω(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| 冒泡排序 | Ω(n) | O(n^2) | O(n^2) | O(1) |
| 插入排序 | Ω(n) | O(n^2) | O(n^2) | O(1) |
| 选择排序 | Ω(n^2) | O(n^2) | O(n^2) | O(1) |
| 树排序 | Ω(n log(n)) | O(n log(n)) | O(n^2) | O(n) |
| 希尔排序 | Ω(n log(n)) | O(n(log(n))^2) | O(n(log(n))^2) | O(1) |
| 桶排序 | Ω(n+k) | O(n+k) | O(n^2) | O(n) |
| 基数排序 | Ω(nk) | O(nk) | O(nk) | O(n+k) |
| 计数排序 | Ω(n+k) | O(n+k) | O(n+k) | O(k) |
| 立方体排序 | Ω(n) | O(n log(n)) | O(n log(n)) | O(n) |
更多
破解编码面试：150个编程问题和解决方案
算法简介，第3版
Java中的数据结构和算法（第二版）
高性能JavaScript（构建更快的Web应用程序界面）
写于 2020年06月15日3525
如非特别注明，文章皆为原创。
转载请注明出处： https://www.liayal.com/article/5ee781217ff0f07e0ea449b5
记小栈小程序上线啦～搜索【记小栈】或【点击扫码】体验
～ 评论还没有，沙发可以有 O(∩_∩)O~