复杂度分析

复杂度分析

复杂度分析是衡量算法执行效率的重要方法。

事后统计法

直接执行代码，并且进行监控统计，获得代码执行效率。

弊端：

• 测试结果依赖测试环境

• 测试结果受数据规模的影响

时间复杂度分析

大O时间复杂度：表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度

分析方法：

• 只关注循环执行次数最多的一段代码

• 加法法则：总复杂度等于量级最大的那段代码的复杂度

• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

同一段代码，在不同输入的情况下，复杂度量级可能会不同。

最好情况时间复杂度分析

最理想情况下，执行这段代码的时间复杂度

最坏情况时间复杂度

最糟糕情况下，执行这段代码的时间复杂度

平均情况时间复杂度

对于所有可能的输入，及其发生的概率，求加权平均，得到的值即为平均情况时间复杂度，也叫加权平均时间复杂度或者期望时间复杂度

均摊时间复杂度

对于复杂度为O(n)的操作，都会跟着n-1个复杂度为O(1)的操作，此时，考察是否可以使用摊还分析，将耗时最多的那次操作，均摊到耗时较少的操作上，从而求得均摊时间复杂度。

空间复杂度分析

空间复杂度：表示代码的存储空间与数据规模的增长关系