# 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)。

```java
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)`。