Skip to content

大O表示法速查表

定义

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