3、复杂度分析：如何分析、统计算法的执行效率和资源消耗？

为什么需要复杂度分析？

　　1、测试结果非常依赖测试环境。测试环境中硬件的不同对测试结果有很大的影响，比如处理器速度。

　　2、测试结构受数据规模的影响很大。比如，对于规模比较小的数据排序，插入排序可能反倒比快速排序要快。

综上，我们需要一个不用具体的测试数据来测试，就可以粗略地计算执行效率的方法，即时间、空间复杂度分析方法。

大O复杂度表示法

int cal(int n){
   int sum = 0;
   int i = 1;
  for(; i<=n; i++){
    sum = sum + i;
}      
  return sum;
}

从CPU的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。第2、3行代码需要1个单位时间unit_time，第4、5分别执行了2n个unit_time执行时间，所以总共执行（2n+2）unit_time。

int cal(int n){
    int sum = 0;
    int i = 1;
    int j = 1;
    for(; i<=n; i++){
     j=1;
     for(; j<=n; j++){
        sum = sum +  i*j;
}
}
}

上述代码中，第2、3、4分别是1个unit_time，5、6行代码是n个unit_time，第7、8行代码循环执行了n*n遍，所以，T（n）= 2*n*n+2*n+3。

上述两种推导过程得到一个结论：所有代码的执行时间与每行代码的执行次数成正比。把这种结论的规律总结成一个公式，即大O：

T（n） = O(f(n))

其中，n表示数据规模的大小；f(n)表示每行代码执行的次数总和。公式中的O，表示代码的执行时间T(n)与f(n)成正比。也可写做O(2n+2)。大O时间复杂度实际上并不具体表示代码的真正执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，所以，也叫渐进时间复杂度（asymptotic time complexity）。当n很大时，公式中的低阶、常量、系数并不能左右趋势，可以忽略。所以，上述也可表示为：T(n)=O(n); T(n)=O(n*n)。

时间复杂度三条使用方法：

1、只关注循环执行次数最多的一段代码

2、加法法则：总复杂度等于量级最大的那段代码的复杂度

3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂度量级

如上图所示，可以粗略地分为两类，多项式量级和非多项式量级，即：指数阶和阶乘阶。我们把时间复杂度为非多项式量级的算法问题叫做NP（Non-Deterministic Polynomial，非确定多项式)问题。当数据规模n越来越大时，非多项式时间复杂度问题的执行时间会无限增大。因此，非多项式时间复杂度的算法其实是非常低效的算法。

空间复杂度，与时间复杂度类似，可以忽略常量存储，常见的空间复杂度为O(1)，O(n)，O(n*n)，空间复杂度比时间复杂度要简单很多。

总结一下，常见的时间复杂度有以下几个。难的需要自己稍微分析。