算法复杂度分析

算法复杂度作用

1. 数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。

2. 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
   O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2 )（平方阶）、O(n^3 )（立方阶）

3. 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，O(2^n )（指数阶）、O(n!)（阶乘阶

4. 算法时间复杂度由小到大依次为：Ο(1)＜Ο(logn)＜Ο(n)＜Ο( nlog^n )＜Ο( n^2 ) ＜Ο( n^3 ) ＜…＜Ο( 2^n ) ＜Ο(n!)
   [图片上传失败…(image-516b81-1554175993123)]

空间复杂度

先说空间复杂度，因为空间复杂度比较简单

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。

我们常见的空间复杂度就是 O(1)、O(n)、O(n)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多

时间复杂度

计算时间复杂度的3个方法

---

1. 只关注循环或递归最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
   (1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
   (2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
   (3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
   (4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
   (5)只需计算基本语句执行次数的数量级，只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

---

例1: O(1)

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

时间复杂度 T(n) = O(2n+2)=O(n)

例2: O( n )

int a=0; //1次频度 
int b=1; //1次频度
for (i=1;i<=n;i++){  //n次频度  
     s=a+b;//n次频度  　　　　 
     b=a;　//n次频度  　　　　   
     a=s;　//n次频度  　　　　
}  

时间复杂度 T(n) = O(4+4n)=O(n)

例3: O( n^2 )

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

时间复杂度 T(n) = O(3+2n+2n*n)=O( n^2 )

例4: O( log^n )

for(i=0;i<n;){//f(n)次频度
    i*=2;//f(n)次频度
}

假设语句2的频度是f(n),则：2^f(n) <=n; f(n)<=log^n ; 取最大值f(n)=log^n ;T(n)=O(log^n )

例5:

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

int x=1; 
for(i=1;i<=n;i++) {
    for(j=1;j<=i;j++){
        for(k=1;k<=j;k++){
            x++; 
        }
    }　　
}

该程序段中频度最大的语句是行号5，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：
则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)

最好、最坏情况时间复杂度

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

因为，要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。

但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。
###平均情况时间复杂度(加权平均时间复杂度 或 期望时间复杂度)

在数组的 0～n-1 位置中要查找的变量 x 在数组中的位置，有 n+1 种情况：不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：
[图片上传失败…(image-f1905f-1554175993123)]

前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：
[图片上传失败…(image-976878-1554175993123)]

引入概率之后，前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。

均摊时间复杂度

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为 count 的位置就可以了，所以最好情况时间复杂度为 O(1)。最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n)。

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：平均时间复杂度是O(1)
[图片上传失败…(image-2a5a12-1554175993123)]

我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)

分析

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}


1. 最好情况时间复杂度为 O(1)
2. 最坏情况分析： 
最坏情况代码执行的次数跟每次数组的长度有关
第1次调用insert的执行的次数为 n ,
第2次调用insert的执行的次数为 2n ,
第3次调用insert的执行的次数为 2^2 * n 
第k次调用insert的执行的次数为 2^(k-1) * n 
最坏时间复杂度为 O(n)。
3. 平均情况分析
当每次遇到最坏情况时数组会进行2倍扩容，原数组被导入新数组，虽然数组的长度变大了，但是插入操作落在的区间的长度是一样的，分别是0~len-1, len~(2len-1),....；
插入的情况仍是len+1种：0~len-1和插满之后的O(len)；所以每次插入的概率是：p= 1/len+1，
最后求出加权平均时间复杂度为 1*p + 2*p+ ▪▪▪ + len*p + len * p = O(1) ; 
4. 均摊时间复杂度 O(1)
而均摊复杂度由于每次O(len)的出现都跟着len次O(1)，是前后连贯的，因而将O(len)平摊到前len次上，得出平摊复杂度是O(1)