复杂度简单的分析

分析、统计算法的执行效率和资源消耗

1. 数据结构和算法本身解决的问题就是"快"和"省"的问题，即如何让代码运行的更快，如何让代码更省存储空间。所以执行效率是一个非常重要的考量指标，而衡量执行效率主要是通过时间和空间复杂度
2. 其实只要是和数据结构以及算法有关，就离不开时间、空间复杂度
3. 通常情况下，我们会通过统计、监控来算法执行的时间和所占内存的大小，但是这种测试结果受测试环境、数据规模影响很大

大O表示法

1. 算法的执行效率，粗略的讲，就是代码的执行时间。在代码运行之前，就可以得到代码的大概执行时间，就是通过时间复杂度分析
2. 如下代码:

1 int cal(int n) {
2        int sum = 0;
3        int i = 1;
4        for (; i <= n; ++i) {
5          5 sum = sum + i;
6        }
7        return sum;       
8    }

3. 从CPU的角度来看，这段代码的每一行都执行者类似的操作，读数据-运算-写数据，虽然每行代码对应的CPU执行的个数，执行的时间都不一样，但是可以粗略的估计出执行时间。假如每行代码的执行时间都一样，为unit_time,在此基础上，这段代码的中执行时间就可以计算出来，第2、3行代码分别需要一个unit_time，第4、5行代码分别运行的n遍，所以需要2n * unit_time，所以总时间为(2n+2)*unit_time，执行时间T(n)与代码的执行执行次数成正比
4. 按照以上分析，如下代码

1 int cal(int n) {
2   int sum = 0;
3   int i = 1;
4   int j = 1;
5   for (; i <= n; ++i) {
6     j = 1;
7     for (; j <= n; ++j) {
8       sum = sum +  i * j;
9     }
10   }
11 }

5. 第2、3、4行代码分别需要一个unit_time，需要2n*unit_time,5、6需要循环n次，7、8执行了n2次，所以需要2n2 * unit_time，总时间为(2n2 + 2n+3) * unit_time.
6. 综上所述，所有代码的执行时间T(n)与每行代码的执行次数n成正比，即大O表示形式为：T(n)=O(f(n)),其中O表示执行时间T(n)与f(n)表达式成正比
7. 以上两个例子中，用大O表示分别为 T(n)=O(2n+2) 、 T(n)=O(2n2 + 2n+3),大O时间复杂度实际上并不是代码的真正执行时间，而是表示代码的执行时间随着数据的规模增长的变化趋势，所以也叫渐进时间复杂度(asymptotic time complexity),简称时间复杂度
8. 当n很大是，达到10000、1000000时，公式中的常量、低阶和系数并不左右增长趋势，所以都可以忽略，只需要记录最大的量级就可以了。所以上面的两个例子就可以表示为T(n)=O(n)、T(n)=O(n2)。

时间复杂度分析

1. 上面第一个案例中，由于常量、低阶和系数不能左右增长趋势，所以总时间复杂度为O(n)
2. 加法法则，代码如下

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

3. 案例中分别为求sum_1、sum_2、sum_3,可以分析每一部分的的时间复杂度，然后放在一起，再取一个量级最大的作为整体的复杂度
4. 第一段代码中，代码执行了100次，所以是一个常量执行时间，跟n的规模无关，而第二段和第三段分别为O(n)、O(n2),取量级最大的时间复杂度，结果为O(n2)，如果将这个规律抽成一个公式，如果T1(n)=O(f(n)),T2(n)=O(g(n)),那么T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n))
5. 乘法法则，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，如案例2

常见的时间复杂度

1. 非多项式量级

• 常量阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
• 线性对数阶 O(nlongn)
• 平方阶 O(n2)、立方阶O(n3)、k次方阶O(nk)

2. 多项式量级

• 指数阶 O(2的n次方)
• 阶乘阶 O(n!)