大O表示法速查表
定义
大O表示法表示算法的最坏情况复杂度。它使用代数术语来描述算法的复杂度，使您能够衡量其效率和性能。下面是一个说明大O复杂度的图表：
简单来说，O(1)表示常数时间复杂度，这是最高效的，而O(n!)表示阶乘时间复杂度，这是最低效的。复杂度中的n表示输入的大小，因此O(n)意味着算法的时间复杂度将随着输入的大小线性增长。
除了大O表示法，还有其他用于描述算法复杂度的符号，例如Ω（Omega）和Θ（Theta）。Ω描述算法的最佳情况复杂度，而Θ描述算法的平均情况复杂度。
常见的数据结构操作
不同的数据结构对于相同的操作具有不同的时间复杂度。例如，链表的插入和删除操作的时间复杂度为O(1)，而数组的时间复杂度为O(n)。下面是常用于Web开发的数据结构的平均和最坏时间复杂度。
平均时间复杂度
| 数据结构 | 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | Θ(1) | Θ(n) | Θ(n) | Θ(n) |
| 队列 | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| 栈 | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| 链表 | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| 双向链表 | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| 跳表 | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) |
| 哈希表 | N/A | Θ(1) | Θ(1) | Θ(1) |
| 二叉搜索树 | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) |
最坏时间复杂度
| 数据结构 | 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) |
| 队列 | O(n) | O(n) | O(1) | O(1) |
| 栈 | O(n) | O(n) | O(1) | O(1) |
| 链表 | O(n) | O(n) | O(1) | O(1) |
| 双向链表 | O(n) | O(n) | O(1) | O(1) |
| 跳表 | O(n) | O(n) | O(n) | O(n) |
| 哈希表 | N/A | O(n) | O(n) | O(n) |
| 二叉搜索树 | O(n) | O(n) | O(n) | O(n) |
数组排序算法
与数据结构类似，不同的数组排序算法具有不同的时间复杂度。下面是最常见的数组排序算法的最佳、平均和最坏时间复杂度。
| 算法 | 最佳情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 快速排序 | Ω(n log n) | Θ(n log n) | O(n^2) |
| 归并排序 | Ω(n log n) | Θ(n log n) | O(n log n) |
| 堆排序 | Ω(n log n) | Θ(n log n) | O(n log n) |
| 冒泡排序 | Ω(n) | Θ(n^2) | O(n^2) |
| 插入排序 | Ω(n) | Θ(n^2) | O(n^2) |
| 选择排序 | Ω(n^2) | Θ(n^2) | O(n^2) |
| 桶排序 | Ω(n+k) | Θ(n+k) | O(n^2) |