大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) |