复杂度分析

复杂度

描述的是随着数据规模n的增大，算法性能变化的趋势。

• 通常看最差的情况
• 算法运行的上界

数据的规模 n
算法的性能 T

复杂度分析**

只考虑算法的性能与数据的规模之间所成的正比关系，记为O(n)



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

递归的时间复杂度与空间复杂度