10.算法分析
算法时间复杂度和空间复杂度
了解时间复杂度对算法的选用会很有帮助，比如说之前怎么样选择数据结构，都是通过每个操作的时间复杂度的分析来看是不是满足需求，肯定的是，在满足需求的情况下，时间复杂度越优越好，操作次数越少越好。
大O是什么？可以理解为操作次数与数据个数的比例关系；O(1)是有限次数的操作；O(n)是操作正比于你的元素。
大O表示法：
参考《算法导论》的列子：考虑计算一个n * n的矩阵所有元素的和：
列举两种方式：
# version1total_sum = 0for 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]# version2total_sum = 0for 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这些。