事后统计法的局限性:
1、测试结果依赖测试环境
2、测试结果受数据规模影响大
大O时间表示法
所有代码的执行时间 T(n) 和每行代码的执行次数是成正比的
T(n) = O( f(n) )
当 n 很大时,公式中的低阶,常量,系数三部分并不左右增长趋势,可以忽略
分析方法:
1、只关注循环最多的一段代码就可以了
2、加法法则:总复杂度等于量级最大的那段代码的复杂度
注意:
循环代码中,只要循环次数是一个已知的数,也是常量级别的执行时间,当n无限大的时候就可以忽略掉,其中可能会影响效率,表示的是 一个算法的执行效率,与数据增长规模的变化趋势,本身对增长趋势并没有影响
公式:
3、乘法法则:嵌套代码的复杂度等于嵌套内外复杂度的乘积
常见时间复杂度:
主要分为:多项式量级和非确定多项式量级
非确定多项式量级:指数阶 , 阶乘阶
多项式量级:常量阶,对数阶,线性阶,线性对数阶,平方阶
1、常数阶
只要算法中不存在循环语句,递归,即使有成千上万行代码,时间复杂度也为O(1)
2、 对数阶和线性对数阶
对数阶 : O( logn )
线性对数阶: 一段时间复杂度为O( logn )的算法执行了n遍,时间复杂度就为O( nlogn)
3、 O(m + n)
当面对两个数据规模 m 和 n ,我们无法评估m 和 n 谁的量级大,计算复杂度的时候,不能简单的利用加法法则省略掉其中一个。