复杂度分析

为什么需要复杂度分析?

把代码跑一遍,通过统计,监控,就能得到算法执行的时间和占用的内存大小. 这种叫事后统计法.

事后统计法有什么局限性:

1. 测试结果依赖测试环境:不同的测试机器,由于机器配置各不相同,得到的结果也截然不同.
2. 测试结果受数据规模的影响很大

   所以我们需要一个不用具体的测试数据来测试,就可以粗略的估计执行效率的方法

   大O复杂度表示法

• 所有代码的执行时间T(n)与每行代码的执行次数成正比.

:代表执行的时间
n:表示数据规模的大小
表示每行代码执行的次数总和.(因为这是一个公式,所以用来表示)
公式中的:表示代码的执行时间与表达式成正比
大时间复杂度实际上并不具体表示代码真正执行的时间,而是表示代码执行时间随数据规模增长的变化趋势,所以也叫做:渐进时间复杂度(asymptotic time complexity),简称时间复杂度.

时间复杂度分析:

1. 只关注循环执行次数最多的一段代码
2. 加法法则:总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则:嵌套代码的复杂度等于嵌套内部代码复杂度的乘积

几种常见时间复杂度实例分析

多项式时间复杂度

1. :一般情况下,只要算法中不存在循环语句,递归语句,即使有成千上万行的代码,其时间复杂度也是
2. 
3. :只关注循环执行最多的那一段代码
4. :由多个参数决定的时间复杂度

越高阶复杂度的算法,执行效率越低.常见的复杂度并不多,从低阶到高阶有:

复杂度分析概念

1. 最好情况时间复杂度(best case time complexity):在最理想情况下,执行这段代码的时间复杂度
2. 最坏情况时间复杂度(worst case time complexity):在最糟糕的情况下,执行这段代码的时间复杂度
3. 平均情况时间复杂度(average case time complexity):用代码再所有情况下执行的次数的加权平均值表示
4. 均摊时间复杂度(amortized time complexity):在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上.基本上均摊结果就等于低级别复杂度.