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)。Last modified 3yr ago