10.算法分析
算法时间复杂度和空间复杂度
了解时间复杂度对算法的选用会很有帮助,比如说之前怎么样选择数据结构,都是通过每个操作的时间复杂度的分析来看是不是满足需求,肯定的是,在满足需求的情况下,时间复杂度越优越好,操作次数越少越好。
大O是什么?可以理解为操作次数与数据个数的比例关系;O(1)是有限次数的操作;O(n)是操作正比于你的元素。
-
大O表示法:
参考《算法导论》的列子:考虑计算一个n * n的矩阵所有元素的和:
列举两种方式:
# version1 total_sum = 0 for i in range(n): row_sum[i] = 0 for j in range(n): row_sum[i] = row_sum[i] + matrix[i, j] total_sum = total_sum + matrix[i, j] # version2 total_sum = 0 for i in range(n): row_sum[i] = 0 for j in range(n): row_sum[i] = row_sum[i] + matrix[i, j] total_sum = total_sum + row_sum[i] # 注意这里和上边的不同
两种方式的主要区别在最后一行,
第一个方式:假设矩阵是n*n的,这嵌套是在两层循环里面,而且每一步都循环n次,可以认为它是一个n*n的,循环两次,即 (2n)*n的时间复杂度。
第二个方式:假设矩阵是n*n的,能看出最后一行不在上面的循环里面,上面的循环执行了n*n(嵌套在两层循环里面),最后一行是执行n次,所以他是n*n+n的时间复杂度。
如果数据量很小,可能感觉不出差异,但是如果放大n的增长的时候,总的操作次数就很明显区别了:
通常不关系每个算法执行了多少次,更关心随输入规模的增加算法运行的时间将以什么样的速度增加,所以定义了一个符号,大O符号。
4. 如何计算时间复杂度
上面举例2个版本的计算矩阵和的代码,有两个公式:
① 2n * n = 2n2
② n+n*n = n+n2
当n非常大的时候,n*n(即n的平方)的数值将占主导,可以忽略单个n的影响:
n+n2<= 2n2
可以认为两个算法的时间复杂度都为O(n2)
5.常用的时间复杂度
列举一些常用的时间复杂度,按照增长速度排序,日常我们的业务代码中最常用的是指数之前的复杂度,指数和阶乘的增长速度非常快, 当输入比较大的时候用在业务代码里是不可接受的。
O | 名称 |
举例 | 补充 |
1 | 常量时间 | 一次赋值 | nlogn以下的这些时间复杂度都是比较占优势的。 |
logn | 对数时间 | 折半查找 | |
n | 线性时间 | 线性查找 | |
nlogn | 对数线性时间 | 快速排序 | |
n2 | 平方 | 两重循环 | 越向上增长的越快那那怕是计算机非常快,依然要花很多时间运行。 |
n3 | 立方 | 三重循环 |
|
2n | 指数 |
递归求斐波那契数列 | |
n! | 阶乘 | 旅行商问题 |
O(1) | 固定时间内的一次操作,比如:一次赋值,一次加法,几次加法操作。 |
O(logn) | 二分查找,操作一个有序数组的时候,每次都可以把它折半。 |
O(n) | 查找都需要从头查到尾,找到了才能退出。 |
O(nlogn) | 快速排序或归并 |
O(n2) | 两重循环嵌套 |
O(n3) | 三重嵌套 |
O(2n) | 指数就有一些递归算法,没有优化的递归 |
O(n!) | 旅行商问题,学术界讨论会比较多,工程会少一些 |
6.空间复杂度
相比于时间,空间很多时候,不是主要的考虑因素,用户老爷们都等不及,而且现在存储都越来越便宜了,为了提升响应速度,能可多用一点空间,所以空间复杂度讨论的少一些;当然,如果数据量非常非常大,也会考虑空间占用的问题。
常见的空间复杂度的增长趋势图:
所以,工程上能接受的都是 nlogn 以下的空间复杂度,图中nlogn,n,log2n这些。