10.算法分析

算法时间复杂度和空间复杂度

1. 了解时间复杂度对算法的选用会很有帮助，比如说之前怎么样选择数据结构，都是通过每个操作的时间复杂度的分析来看是不是满足需求，肯定的是，在满足需求的情况下，时间复杂度越优越好，操作次数越少越好。

2. 大O是什么？可以理解为操作次数与数据个数的比例关系；O(1)是有限次数的操作；O(n)是操作正比于你的元素。

3. 大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 = 2n²

② n+n*n = n+n²

当n非常大的时候，n*n(即n的平方)的数值将占主导，可以忽略单个n的影响：

n+n²<= 2n²

可以认为两个算法的时间复杂度都为O(n²)

5.常用的时间复杂度

列举一些常用的时间复杂度，按照增长速度排序，日常我们的业务代码中最常用的是指数之前的复杂度，指数和阶乘的增长速度非常快， 当输入比较大的时候用在业务代码里是不可接受的。

6.空间复杂度

    相比于时间，空间很多时候，不是主要的考虑因素，用户老爷们都等不及，而且现在存储都越来越便宜了，为了提升响应速度，能可多用一点空间，所以空间复杂度讨论的少一些；当然，如果数据量非常非常大，也会考虑空间占用的问题。

常见的空间复杂度的增长趋势图：

所以，工程上能接受的都是 nlogn 以下的空间复杂度，图中nlogn，n，log2n这些。