复杂度分析

时间复杂度

渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

O(1)

常量级的时间复杂度，代码计算规模不随着n增长而增长，如下代码：

int i = 1; 
int j = 2;
int sum = i + j;

O(logn)、 O(nlogn)

对数阶时间复杂度比较难分析，可以通过下面的代码看：

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

容易看出，算上面的时间复杂度，主要是算出第 3 行执行了多少次。列出公式：

$2^x = n$

只要求出 x 值，就可以得到时间复杂度，由高中知识可知：

$x = log_2n$

所以，复杂度是O($log_2n$)。

下面我们稍微改下代码：

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

易得时间复杂度是 O($log_3n$)。

因为对数之间是可以互相转换的：

$log_3n = log_32 * log_2n$

$log_3n = C * log_2n$

我们知道在时间复杂度的计算中，常数 C 是可以省略掉的，因此：

O($log_3n$) = O($log_2n$)

所以对数的底可以直接忽略掉，为O($logn$)。

时间复杂度O($nlogn$)就是把时间复杂度为O($logn$)的代码执行 n 次。

O(m + n), O(m * n)

这种类型的时间复杂度由两块代码的数据规模共同决定，他们不是常数，比如：

void cal(int m, int n)
{
  int sum1, sum2, i, j;
  i = j = 0;
  sum1 = sum 2 = 0;
  for(i = 0; i < m; i++)
  {
    sum1 += i;
  }
  for(j = 0; j < n; j++)
  {
    sum2 += j;
  }
  
  return sum1 + sum2;
}

这里的时间复杂度由 m 和 n 的规模共同决定，故上面代码时间复杂度是 O(m + n)。

稍微改下代码：

void cal(int m, int n)
{
  int sum, i, j;
  i = j = 0;
  sum = 0;
  for(i = 0; i < m; i++)
  {
      for(j = 0; j < n; j++)
    {
            sum += i * j;
    }
  }
  
  return sum;
}

故上面代码时间复杂度是 O($m \times 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 的话，那么时间复杂度是O(1)；如果到数组的最后才找到的话， 那么时间复杂度是O(n)。

平均时间复杂度

但是这两种情况都是最极端的情况，我们需要分析更可能出现的情况的概率，所以这里引入一个新的概念：平均时间复杂度。

还是上面的例子，我们分析，从概率论上说，这个数字找到和找不到的概率都是 $\frac{1}{2}$ ，然后出现在 0 和 n - 1 这 n 个位置上的概率是 $\frac{1}{n}$。所以把各种情况都考虑进去的话， 平均时间复杂度的计算过程变成了：

$1 \times \frac{1}{2n} + 2 \times \frac{1}{2n} + \cdots + n \times \frac{1}{2n} + \frac{n}{2}$

$ = \frac{1}{2n} \times (1 + 2 + \cdots + n) + \frac{n}{2}$

$= \frac{1}{2n} \times \frac{(1+n)\times n}{2} + \frac{n}{2}$

$= \frac{1+n}{4} + \frac{2n}{4}$

$= \frac{3n + 1}{4}$

知道可以忽略复杂度中的系数和常数

O (n) = $\frac{3n + 1}{4} = \frac{3}{4}n + \frac{1}{4} =$ O(n)

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

空间复杂度

渐进时间复杂度，表示算法的存储空间与数据规模之间的增长关系。

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]
  }
}

这里的空间复杂度只跟第 3 行的 n 有关系，也就是O(n)。就是这么简单，常用的空间复杂度一般有
O(1)、O(n)和O($n^2$)。

总结

越高阶的复杂度，效率越是低下；
时间复杂度从O(1), O($logn$), O(n), O($nlogn$), O($n^2$)依次递增；
空间复杂度一般是O(1)、O(n)和O($n^2$)。

参考文献：
数据结构与算法之美 - 王争