解决同一个问题的多种方法的好坏区分？

执行效率是算法一个非常重要的考量，如何衡量一个算法的执行效率呢？
数据结构和算法本身的为了解决“快”和“省”的问题，所谓的“快”和“省”具体指什么？

代码运行的时间更快，运行占用的空间更少！
快-时间复杂度
省-空间复杂度

为什么要进行复杂度分析

大家知道我们程序写出来，运行一遍就知道占用的内存大小，那么为什么还要做复杂度分析呢？运行程序得出的结果在专业上叫着事后统计法
事后统计法的缺点：

测试依赖于环境，不同的环境显示结果不一样
测试结果受数据规模影响很大

基于上诉原因，我们需要一个不需要具体的测试数据就能粗略估计算法执行效率的方法

为什么要进行时间复杂度分析

如何在不执行代码的情况下，分析代码的执行效率？从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_timen²=(2n+2n²)*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 的取值就是一个等比数列 2⁰ 2¹ 2² 2³ 2ⁱ==n ,所以代码执行的次数i=log2ⁿ

对数阶时间复杂度非常常见,但是非常难以分析

修改代码后，变量 i 的值从 1 开始取，每循环一次就乘以 3 。当大于 n 时循环结束，所以变量 i 的取值就是一个等比数列 3⁰ 3¹ 3² 3³ 3ⁱ==n ,所以代码执行的次数i=log3ⁿ

对数之间是可以互相转换的，log3ⁿ就等于log3² * log2ⁿ，所以O(log3ⁿ) = O(C * log2ⁿ)，其中C=log 3 2是一个常量。基于我们前面的一个理论：在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n))。所以，O(log2ⁿ) 就等于O(log3ⁿ)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn) 。