1.2 复杂度分析
1.2 复杂度分析
想要学习数据结构与算法,首先要掌握一个最重要的概念——复杂度分析,它可以帮我们分析如何更省、更快地存储和处理数据。
时间复杂度
算法的 时间复杂度(time complexity) 是一个函数,它定性描述该算法的运行时间。用于评估执行程序所消耗的时间,可以估算出程序对处理器的使用程度。
时间复杂度常用大 O 符号表述,使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
相同大小的不同输入值仍可能造成算法的执行时间不同,因此我们通常使用算法的最坏情况复杂度,记为 T(n)
,定义为任何大小的输入 n 所需的最大执行时间。
以下是一些最常用的 大 O 标记法 列表以及它们与不同大小输入数据的性能比较。
大 O 标记法 | 计算 10 个元素 | 计算 100 个元素 | 计算 1000 个元素 |
---|---|---|---|
O(1) | 1 | 1 | 1 |
O(log N) | 3 | 6 | 9 |
O(N) | 10 | 100 | 1000 |
O(N log N) | 30 | 600 | 9000 |
O(N^2) | 100 | 10000 | 1000000 |
O(2^N) | 1024 | 1.26e+29 | 1.07e+301 |
O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
数据结构操作的复杂性
数据结构 | 连接 | 查找 | 插入 | 删除 | 备注 |
---|---|---|---|---|---|
数组 | 1 | n | n | n | |
栈 | n | n | 1 | 1 | |
队列 | n | n | 1 | 1 | |
链表 | n | n | 1 | 1 | |
哈希表 | - | n | n | n | 在完全哈希函数情况下,复杂度是 O(1) |
二分查找树 | n | n | n | n | 在平衡树情况下,复杂度是 O(log(n)) |
B 树 | log(n) | log(n) | log(n) | log(n) | |
红黑树 | log(n) | log(n) | log(n) | log(n) | |
AVL 树 | log(n) | log(n) | log(n) | log(n) | |
布隆过滤器 | - | 1 | 1 | - | 存在一定概率的判断错误(误判成存在) |
数组排序算法的复杂性
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | in-place | 稳定 |
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | in-place | 不稳定 |
插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | in-place | 稳定 |
希尔排序 | O(nlogn) | O(nlog^2n) | O(nlog^2n) | O(1) | in-place | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | out-place | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | in-place | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | in-place | 不稳定 |
桶排序 | O(n+k) | O(n+k) | O(n^2) | O(n+k) | out-place | 稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | out-place | 稳定 |
基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | out-place | 稳定 |
分析复杂度的一些规则
- 多个时间复杂度相加,如果都是与 n 相关,则取取复杂度高的那一个,例如:
O(nlogn + n) = O(nlogn),O(nlogn + n^2) = O(n^2)
。 - 多个时间复杂度相加,如果其中有些项的复杂度和 n 不相关则不能忽略任何项,例如:
O(AlogA + B),O(AlogA + B^2)
- 两个循环依次执行,则取复杂度高的那个,嵌套多个循环则需要累乘复杂度。
一个时间复杂度分析的例子:
有一个字符串数组,将数组中的每个字符串按照字母排序,然后在将整个字符串数组按照字典顺序排序。求整个操作的时间复杂度。
我们来分析一下,假设最长字符串的长度是 s,数组中有 n 个字符串。
对每个字符串排序
O(slogs)
,将数组中的每个字符串按照字母排序O(n * slogs)
;将整个字符串数组按字典排序
O(s * nlogn)
;所以最后的时间复杂度是
O(n * slogs) + O(s * nlogn) = O(nslogs + nslogn) = O(ns * (logs+logn))
时间复杂度优化
- 采用更好的算法:举例:
1+2+3...n
从1~n
求和,直接循环法,for i->n: sum+=i
,我们也可以用求和公式:n(n+1)/2
;有些问题可以用二分查找等。 - 空间换时间,比如用 set 或 map 加快查找的速度,用二叉搜索树或者字典树加快字符串的搜索。
空间复杂度
空间复杂度(Space Complexity) 指的是算法在运行过程中所占存储空间的大小,依然使用大 O 来表示。用于评估执行程序所占用的内存空间,可以估算出程序对计算机内存的使用程度。
常见的空间复杂度
- 一维数组空间,如果存储了 n 个元素,空间复杂度
O(n)
; - 二维数组空间,总共有 n 个数组,每个数组存储了 n 个元素,空间复杂度
O(n^2)
; - 常数空间复杂度
O(1)
;