解决同一个问题的多种方法的好坏区分？
执行效率是算法一个非常重要的考量，如何衡量一个算法的执行效率呢？
数据结构和算法本身的为了解决“快”和“省”的问题，所谓的“快”和“省”具体指什么？
- 代码运行的时间更快，运行占用的空间更少！
- 快-时间复杂度
- 省-空间复杂度
为什么要进行复杂度分析
大家知道我们程序写出来，运行一遍就知道占用的内存大小，那么为什么还要做复 杂度分析呢？运行程序得出的结果在专业上叫着事后统计法
事后统计法的缺点：
- 测试依赖于环境，不同的环境显示结果不一样
- 测试结果受数据规模影响很大
基于上诉原因，我们需要一个不需要具体的测试数据就能粗略估计算法执行效率的 方法
为什么要进行时间复杂度分析
如何在不执行代码的情况下，分析代码的执行效率？ 从CPU的角度来看，对于每一行代码做的都是同一件事，读数据-运算-写数据
- 时间复杂度分析-实例1
假设每行代码对应的CPU执行时间一样为一个时间单位unit_time。可以看到这个函数代码第2，5行执行1次，第3，4行执行了n次，总共执行时间计算：
T(n)=2unit_time+2unit_timen=(2+2n)*unit_time
- 时间复杂度分析-实例2
假设每行代码对应的CPU执行时间一样为一个时间单位unit_time。可以看到这个函数代码第2，5行执行n次，第3，4行执行了nxn次，总共执行时间计算：
T(n)=2unit_timen+2unit_timen2=(2n+2n2)*unit_time
时间复杂度分析
尽管我们不知道一个unit_time的具体时间是多少，但是我们通过实例1和实例2可以推 导出代码是执行时间与执行次数n正比，我们讲这个规律总结成公式
T(n) = O(f(n))
• T(n)：代码的执行时间
• n：数据的规模
• f(n)：每行代码执行的次数总和
• O：表示T(n)与f(n)正比关系
大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据 规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度
时间复杂度分析
当 n 很大时，你可以把它想象成 10000 、 100000 。而公式中的低阶、常量、系数三 部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以 了，如果用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为：
实例一：T(n) = O(n)；
实例二：T(n) = O(n2 )；
注意!!!即便某一段代码循环 10000 次、 100000 次，只要是一个已知的数，跟 n 无关， 照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略.
如何对一段代码进行时间复杂度分析
1. 只关注循环执行次数最多的一段代码：
大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、 低阶、系数，只需要记录一个最大阶的量级就可以了，分析一个算法、一段代码的 时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了
2. 总复杂度等于量级最大的那段代码的复杂度
3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积-实例2
几种常见的时间复杂度实例分析
常见复杂度量级详解-非多项式量级
数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执 行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法
常见复杂度量级详解-多项式量级O(I)
O(I) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如 下面这段代码，即便有 5行，它的时间复杂度也是 O(I）
• print(1)
• print(2)
• print(3)
• print(4)
• print(5)
常见复杂度量级详解-多项式量级O(LOGN)
对数阶时间复杂度非常常见,但是非常难以分析
通过前面的复杂度分析方法知道第3，4行代码是执行次数最多的行数，要求出这段代码的时间复杂度，我 们只需要求出第3，4行代码的执行次数即可
变量 i 的值从 1 开始取，每循环一次就乘以 2 。当大于 n 时循环结束，所以变量 i 的取值就是一个等比 数列 20 21 22 23 2i==n ,所以代码执行的次数i=log2n
对数阶时间复杂度非常常见,但是非常难以分析
修改代码后，变量 i 的值从 1 开始取，每循环一次就乘以 3 。当大于 n 时循环结束，所以 变量 i 的取值就是一个等比 数列 30 31 32 33 3i==n ,所以代码执行的次数i=log3n
对数之间是可以互相转换的，log3n就等于log32 * log2n，所以O(log3n) = O(C * log2n)，其中C=log 3 2是一个常量。基于我们前面的一个理论：在采用大O标记复 杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示 为 O(logn) 。
常见复杂度量级详解-多项式量级O(NLOGN)
理解了O(logn) ，那 O(nlogn) 就很容易理解了。如果一段代码的时间复杂度是 O(logn) ，同时循环 执行 n 遍，时间复杂度就是 O(nlogn) 了
常见复杂度量级详解-多项式量级O(M+N)、O(M*N)
