Complexity

时间复杂度

代码的执行总时间T(n)与所有行代码的执行总次数f(n)成正比，即：

T(n) = O(f(n))

n 表示数据规模大小，O 表示正比例函数。

大 O 时间负复杂度并不代表代码真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当n很大时，f(n)中的低阶、常量、系数并不影响增长趋势，所以可以忽略，如O(2n^2+2n+3)可表示为O(n^2)。所以时间复杂度分析有一些实用技巧：

1. 只关注循环次数最多的一行代码。

2. 加法法则，总复杂度等于量级最大的复杂度。如，有两段先后执行的代码复杂度分别为O(n)与O(n^2)，那么总的复杂度为O(n^2)。

3. 乘法法则，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。如，有两段嵌套的代码复杂度分别为O(n)与O(n^2)，那么总的复杂度为O(n^3)。

几种常见的时间复杂度：

# 多项式量级
O(1) //常量阶
O(logn) //对数阶
O(n) //线性阶
O(nlogn) //线性对数阶，如归并排序、快速排序
O(n^2) //平方阶
O(n^3) //立方阶
O(n^k) //k次方阶
​
# 非多项式量级
O(2^n) //指数阶
O(n!) //阶乘阶

我们把非多项式量级的算法问题称为 NP 问题（Non-Deterministic Polynomial）。

当一段代码的复杂度由两个数据规模来决定，并且不知道两个数据规模量级谁的大，那么复杂度对加法规则是： O(f(m) + f(n)) ，乘法规则是：O(f(m) * f(n)) 。

不同情况下的复杂度

• 最好情况时间复杂度（best case time complexity）

• 最坏情况时间复杂度（worst case time complexity）

• 平均情况时间复杂度（average case time complexity）

同一代码块在不同情况下，时间复杂度有量级差距，我们就需要使用上述三种复杂度表示。比如下面代码，在数组中查找数据，最好 O(1)，最坏 O(n)，平均 O(n)。

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

摊还分析

对一个数据结构进行连续操作，大部分情况时间复杂度很低，只有个别情况时间复杂度很高，而且这些操作之间存在前后关系，这时，可以将这组操作一起分析，看能否把时间复杂度较高的操作平摊到其它时间复杂度较低的操作。摊还分析得到的时间复杂度为均摊时间复杂度（amortized time complexity）。

本质上均摊时间复杂度是一种特殊的平均时间复杂度，一般两者相等。

空间复杂度

渐进空间复杂度（asymptotic space complexity）表示算法的存储空间与数据规模之间的增长关系。

常用空间复杂度：O(1)、O(n)、O(n^2)。