#####为什么需要复杂度分析?
1
2
3
4
5
6
7
8
9
| 通过监控得到的时间和内存占用是正确的、有些地方称为: 事后统计法
但事后统计有很大的局限性:
1. 测试结果严重依赖测试环境
机器配置和设置都会导致测试结果的差异
2. 受数据规模的影响较大
eg. 对于同一排序算法、待排序数据的有序度不同、排序得到的时间差别会比较大、也会受数据本征的影响. 若原数据有序、对有些算法来说 可能不需要任何操作、会特别快
另: 数据规模较小时、可能无法反馈出排序算法的性能
所以、需要一个不受测试数据和测试环境影响、可以用来粗略计算算法执行效率的方法。
|
大O复杂度表示法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 算法的执行效率简单来说、就是算法代码执行的时间
eg. 下边代码
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
从CPU的角度来看、每一行都有类似的操作: 读数据-运算-写数据
尽管每行代码对应的CPU执行的个数、执行的时间都不同、但对于粗略估计、可以认为是相同的, 假设为: unit_time
第4、5行运行了n遍、需要2n*unit_time, so. 总共需要 (2n+2)*unit_time
所有代码的执行时间 T(n) 与执行次数成正比
将改规律记为:
T(n) = O(f(n))
T(n):执行时间 n:数据规模 f(n):每行代码的执行次数总和、就是大O时间复杂度表示法
大O时间复杂度只是代表执行时间随数据规模增长的变化趋势、而不是真正的代码执行时间、也叫 渐进时间复杂度
|
时间复杂度分析
1
2
3
| 1. 只关注执行次数最多的代码
2. 加法法则: 总复杂度等于量级最大的代码的复杂度
3. 乘法法则: 嵌套代码的复杂度=嵌套内外代码复杂度的乘积
|
常见复杂度量级
1
2
3
4
5
6
7
8
9
| 常量阶 O(1)
对数阶 O(log n)
线性阶 O(n)
线性对数阶 O(nlog n)
平方阶 O(n<sup>2</sup>)、立方阶 O(n<sup>3</sup>)、... K次方阶 O(n<sup>k</sup>)
指数阶 O(2<sup>2</sup>)
阶乘阶O(n!)
可以粗略的分为 多项式量级和非多项式量级(指数阶 和 阶乘阶)、把时间复杂度为非多项式量级的算法问题叫 NP问题、当n的规模增大时、非多项式量级算法很低效
|
复杂度量级简单说明
1
2
3
4
5
6
7
8
9
| 1. O(1)
常量级复杂度、一般只要算法中不存在循环、递归语句、代码行再多、时间复杂度也是 O(1)
2. O(logn)、O(nlogn)
对数阶复杂度(归并排序、快速排序的时间复杂度都是O(nlogn)
eg. i=1;while(i<n){i = i*3;}
3. O(m+n)、O(m*n)
明显有m和n两个数据规模的示例
|
空间复杂度
时间复杂度的全称是: 渐进时间复杂度、表示算法的执行时间与数据规模之间的增长关系
类比: 空间复杂度 –> 空间渐进复杂度、表示算法的存储空间与数据规模之间的增长关系
1
| 常用的空间复杂度只有: O(1)、O(n)、O(n<sup>2</sup>)
|