复杂度分析

为什么需要复杂度分析?

通过监控得到的时间和内存占用是正确的、有些地方称为: 事后统计法
但事后统计有很大的局限性:
1. 测试结果严重依赖测试环境
   机器配置和设置都会导致测试结果的差异
2. 受数据规模的影响较大
   eg. 对于同一排序算法、待排序数据的有序度不同、排序得到的时间差别会比较大、也会受数据本征的影响. 若原数据有序、对有些算法来说 可能不需要任何操作、会特别快
   另: 数据规模较小时、可能无法反馈出排序算法的性能
   
所以、需要一个不受测试数据和测试环境影响、可以用来粗略计算算法执行效率的方法。

大O复杂度表示法

算法的执行效率简单来说、就是算法代码执行的时间

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. 乘法法则: 嵌套代码的复杂度=嵌套内外代码复杂度的乘积

常见复杂度量级

常量阶 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. 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两个数据规模的示例
   

空间复杂度

时间复杂度的全称是: 渐进时间复杂度、表示算法的执行时间与数据规模之间的增长关系

类比: 空间复杂度 --> 空间渐进复杂度、表示算法的存储空间与数据规模之间的增长关系

常用的空间复杂度只有: O(1)、O(n)、O(n<sup>2</sup>)