复杂度分析的目的

  数据结构与算法本身是为了解决快和省的问题，所以执行效率是衡量算法好坏的一个非常重要的指标，如何判断执行效率？一般是通过时间、空间复杂度分析来衡量算法的执行效率。

常见分析算法执行效率的方法

事后统计法

  通过监控将代码在测试机器上直接运行来统计算法内存大小占用和执行时间快慢的方法叫做事后统计法。
 
    1. 测试结果非常依赖测试环境。例如：相同代码在i9处理器比在i3处理器上面运行的更快。
    2. 测试结果受数据规模的影响很大。比如：对于小规模的排序来说，插入排序(时间复杂度 = )可能比快速排序(平均时间复杂度 = nn)要快。

小结：所以，我们需要一个不用依赖测试环境和测试数据就可以粗略的估算算法执行效率的方法--时间、空间复杂度分析 。

时间复杂度分析引入--大O复杂的表示法

  代码执行效率粗略来说就是代码执行的时间，从CPU角度分析，代码执行都是类似操作：读数据--运算--写数据。假设每行代码的执行时间都相同，为unit_time，那么代码总执行时间=各个代码执行时间之和，即--代码总执行时间T(n)与每行代码执行次数n成正比。

T(n) = O(F(n))

时间复杂度分析

  时间复杂度又叫渐进时间复杂度，表示算法执行时间与数据规模之间的增长关系。

时间复杂度分析方法

  1. 只关注循环执行次数最多的一段代码。
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度。
  3. 乘法法则：嵌套代码的复杂的等于嵌套内外代码复杂的的乘积。

复杂度量级
  对于上图罗列的复杂度量级一般分为两类：多项式量级和非多项式量级，常见的非多项式量级是O()和O(n!)。
  非多项式量级:又叫做NP(Non-Deterministic Polynomail 非确定多项式)问题，特点：复杂度随着n的增大急剧增加，是比较低效的算法。

  常见的多项式时间复杂度

  1. O(1) ：常量级时间复杂度，特点：时间复杂度不随着n的变化而变化。一般算法中不存在循环、递归；即使有成千上万行代码，其时间复杂度也是O(1) 。
  2. O(n) 、O(nn) ：对数阶时间复杂度。

public int sum( int n){
      int i = 1;
      while(i <= n){
          i = i*2;
      }
     return i;
}

从上面可以看出，这段代码时间复杂度x和数据n是等比数列的关系-- x = n,注意在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n)),因此对数阶时间复杂度统一表示为：O(n)。那么O(nn) = O(n) * O(n)，即：乘法法则

... = n

  3. O(m+n)、O(m*n) ：时间复杂度由两个数据规模决定。因为无法事先评估m 和n谁的量级大，所以加法法则不在适用，但是乘法法则则继续有效。

空间复杂度

  空间复杂度又叫渐进空间复杂度，表示算法存储空间与数据规模之间的增长关系。常见的复杂的从低阶到高阶有：O(1)、O(n)、O()。

总结

  复杂度也叫渐进复杂度，包括时间和空间（两个维度，目的是脱离运行环境来分析算法执行效率与数据规模之间的增长关系，越高阶复杂度算法，执行效率越低，常用复杂度从低到高排序：O(1)、O(n)、O(n)、O(nn)、O() 。