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