第一周_复杂度分析

前言

复杂度分析给我们提供了一个很好的理论分析的方向，并且它是宿主平台无关的，能够让我们对代码执行上性能和效率上有一个感性的认知。

时间复杂度

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 }

以大O时间复杂度表示法：

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫做渐进时间复杂度，简称时间复杂度。

当 n 很大时，我们可以省略低阶、常量和系数部分，所以以上代码以大O时间复杂度表示为：

分析时间复杂度，有三个实用的方法：

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

常见时间复杂度

• 常数阶 O(1)

  O(1) 只是常量阶时间复杂度的一种表示方法，并不是指只执行了一行代码。或者说，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)。

• 对数阶 O(logn)、O(nlogn)

  对数时间复杂度非常常见，最常见于while循环中。

  1 i=1;
  2 while (i <= n)  {
  3   i = i * 2;
  4 }
  

  以上代码时间复杂度可表示为：
  
  实际上，不管是以 2 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为：
  
  对于以上代码，如果在最外层又循环执行了 n 遍，那么就是 O(nlogn)。O(nlogn)也是一种非常常见的算法时间复杂度，比如归并排序、快排的时间复杂度都是O(nlogn)。

• 多项式量阶 O(m+n)、O(m*n)

  只不过由两个变量所影响而已。

空间复杂度

其实空间复杂度分析相对于时间复杂度分析来说是非常容易的，我们只需要关注有没有新的空间被申请。

1 void print(int n) {
2    int i = 0;
3    int[] a = new int[n];
4    for (i; i <n; ++i) {
5      a[i] = i * i;
6    }

7    for (i = n-1; i >= 0; --i) {
8      print out a[i]
9    }
10 }

在第二行代码中申请了一个空间，不过是常量阶的，跟规模 n 没有关系，可以忽略。在第三行申请了一个大小为 n 的 int 类型数组，除此之外，没有任何空间被申请了，所以，这段代码的空间复杂度就是：

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

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

最好情况时间复杂度为：O(1)

最坏情况下时间复杂度为：O(n)

平均时间复杂度

还是对于以上代码，一共有 n+1 种情况：在数组中(0 ~ n-1)和不在数组中，平均值：

去掉系数以及常量等等，得到平均时间复杂度为：

但是这样考虑是有问题的，因为对于这 n+1 种情况，并不是每种情况出现的概率都是一样的。对于，在数组中和不在数组中的概率都为1/2，所以，平均时间复杂度的计算过程就变成了：

这个值就是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度