数据结构与算法之美（一）

数据结构与算法之美（一）

1.复杂度分析

数据结构和算法本身解决的是“快”和“省”的问题，即让代码运行地更快，更省内存空间。

为什么需要复杂度分析：

需要一个不用具体测试数据来测试，就可以粗略地估计算法执行效率的方法。

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

首先看下上面的代码，执行的就是1-n的累加操作，从CPU的角度来看，每一行执行的操作都是类似的：读数据-运算-写数据，我们把这个操作执行的时间定义为unit_time（单位时间），在这个基础之上，估算整个代码需要执行多久（多少次这样的unit_time）。不难看出，它执行的总时间是T(n)=(2+2n)unit_time。

同样的在看到下面的代码：

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)=(2n*n+2n+3)unit_time。

我们不必要知道unit_time的具体值是多少，从上面两次分析中可以得出一个规律， T(n)与每行代码执行次数n成正比。我们用大O（bigO）来表示这种关系。

于是有了第一个例子的T(n)=O(2+2n)，第二个例子的T(n)=O(2n*n+2n+3)，需要注意的是，大O时间复杂度表示的是代码执行时间随数据规模增长的变化趋势，而不是代码真正的执行时间，所以也叫它渐进时间复杂度，就是我们常说的时间复杂度。

通常，我们考虑时间复杂度是针对n很大的情况下，当n很大的时候，我们可以忽略掉bigO表达式中的常数项，低阶项以及系数，只考虑最高次项本身。就前面两段代码，他们的时间复杂度分别为O(n)和O(n^2)。

时间复杂度分析：

对于时间复杂度分析，有以下几个比较实用的方法

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

那些常量级和低阶级的执行时间不考虑到总的时间复杂度中来。

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

int cal(int n) {
    //1
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }
    //2
   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
     //3
   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;
 }

对于上面那段代码，分成三部分，第一部分的时间复杂度是常量级的（一段代码的执行次数只要它是一个已知的数它就是常量级的，不管这个数是100,10000，10000000亦或是更大），第二段代码的时间复杂度是O(n)，第三段代码的时间复杂度是O(n^2)，所以最后整段代码的最终时间复杂度就是O(n^2)，因为当随着n增长越来越大的时候，对整个时间复杂度影响最大的是第三段代码而不是前面的。bigO描述的也只是这种变化趋势而已。

时间复杂度分析的加法法则还可以用公式来描述：

T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

3.乘法法则：

嵌套代码的复杂度等于嵌套内外层代码复杂度的乘积。

T(n)=T1(n) T2(n)=O(f(n)) O(g(n))=O(f(n)*g(n))

举个例子：

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

1处代码的时间复杂度是O(n)，调用到的f(i)函数的时间复杂度2也是O(n)，整个代码就相当于嵌套循环一样，最终整个程序的时间复杂度就是O(n^2)。

几种常见的时间复杂度分析：

对于非多项式量级，当随着n的规模越来越大的时候，算法的执行时间会急剧增加，求解问题的时间会无限增长，对于这种低效的算法，直接跳过就行。

1.O(1)：

这表示常量级的时间复杂度，而不是说代码只执行了一次或者一行，只要某段代码的执行次数是一个已知数，那么它的时间复杂度就是O(1)。

2.O(logn)，O(nlogn)

首先来看对数阶的例子

//影响最大的代码执行时间log2 N 
i=1;
 while (i <= n)  {
   i = i * 2;
 }
//影响最大的代码执行时间log3 N
 i=1;
 while (i <= n)  {
   i = i * 3;
 }

我们知道，对数之间是可以互相转换的，log3n就等于log3 2 log2n，所以O(log3n) = O(C log2n)，其中C=log3 2是一个常量，在bigO表示法中可以忽视掉，故而所有存在这种成对数关系的时间复杂度中，均可以忽略掉底数，而最终记为O(logn)。

而O(nlogn)则可以用乘法法则反推过来，它的情况就是，O(n)嵌套O(logn)。

3.O(m+n)，O(m*n)

这两种情况指的是，当代码的复杂度是由两个数据的规模来决定的时候，我们无法再像前面那样有一个明确的谁是量级最大的，所以我们需要将m和n都考虑进来。

例如下面的代码：

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
  return sum_1 + sum_2;
}

上面的代码，时间复杂度是O(m+n)，当确定了m和n谁是最高量级的时候，就可以归入到前面说到的情况了。而对于这种复杂度依赖于两个不确定的数据的规模情况，加法法则不再是取max，而是要将他们统一纳入到O中，乘法法则可以继续有效。

空间复杂度分析：

看这段代码：

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

上面的代码中，只有第2,3行申请了额外的内存空间，那么对于空间复杂度的分析也正是就这种申请了额外的存储空间的代码而言的。很明显，按照bigO表示法的意义，最终这段代码的空间复杂度是O(n)。

对空间复杂度的分析基本上就上面的方法。

最好，最坏，平均，均摊时间复杂度：

为了引出这几个概念，先看下面的一段无须查找的代码：

// 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;
}

上面这段代码，去掉break和加上break，对代码复杂度分析是完全不一样的，当没有break的时候，这段代码的时间复杂度就是bigOn，但是当优化加上break之后，它不再是如此了。

可能说一次就找到了，可能说10次就找到，可能说n次就找打了，可能n次也找不到。

为了表示代码在不同情况下的不同时间复杂度，引入了最好，最坏，平均情况时间复杂度。而他们的含义也是见名知意的。拿上面的代码举例，最好情况就是一次找到，最坏就是需要对整个数据都进行遍历才行。

平均时间复杂度

那么对于平均时间复杂度而言，拿上面的查找代码为例，分析过程就是：对于search key x而言，它能出现的位置一共有n+1种可能（前面的n种表示在这个数组中，而第n+1种则是指x不在数组中），如果把需要每一种情况下需要遍历的元素累加，然后再除以n+1，就可以得到求得结果（找到或者未找到）所需要遍历元素的平均值。

于是我们得到了这个公式：

公式中，累加了两次n，一次是找到了，一次是未找到，最后得到的平均复杂度就是O(n)。

上面虽然得到了正确的时间复杂度，但是过程却不一定正确，不妨这样想，1次就找到和100次才找到，这两个时间的概率并不相等，后者的概率显然大于前者（因为随着查找次数增加，后面继续查找下去找打的概率就越大），所以上面的n+1种情况并不等概率发生，如果把经过m次查找看做一个随机事件，我们还需要给它加上一个权值，这个权值就是经过m次查找找到的概率。

x在不在数组中的概率都是1/2，而要查找的数据出现在0-（n-1）这n个位置上的概率也是相等的1/n，所以在0-（n-1）这n个位置上找到x的概率就是1/2n，那么经过m次查找可能得到结果的概率就是m*1/2n。

所以我们得到了下面这个公式：

需要解释的一点是最后一个n*1/2，这是x不在数组中的情况，概率是1/2，需要总共要遍历n个元素。最后把加权平均值相加，得到加权平均时间复杂度O(n)。

而平均时间复杂度，就是用代码在所有情况下执行次数的加权平均值表示。

均摊时间复杂度

这实际上是一种特殊情况下的复杂度，举个例子，假设存在n-1次常量级的操作，在第n-1次之后又加上一次O(n)的操作，均摊分析的思路大致思路就是，像这种情况，我们可以把耗时多的操作均摊到耗时少的n-1次操作上，均摊下来的时间复杂度就是均摊时间复杂度。

对于均摊时间复杂度，使用的情况比较少，总结下它的应用场景就是：

对一个数据结构进行连续的操作，其中大部分的操作时间复杂度都比较的低，之后个别情况下的复杂度较高，而且这一系列操作在时序上是前后连贯的，这个时候我们就可以将复杂度高的操作耗时平摊到复杂度低的操作上，而如果能够应用到均摊时间复杂度的场合，一般而言 ，均摊时间复杂度往往就是最好情况时间复杂度。

可以认为均摊时间复杂度是一种特殊的平均时间复杂度，对此我们不必花太大经历去区分他们，重点在于怎么去分析平均时间复杂度和均摊时间复杂度。