递归函数
递归函数是指在函数定义中调用函数自身的方法。分析递归函数的复杂度通常需要建立递推关系式。
递归分析框架
- 确定递归关系：T(n) 与 T(subproblems) 的关系
- 确定基准条件：递归终止时的复杂度
- 求解递推式
求解方法
- 代入法：猜测上界，通过数学归纳法证明
- 递归树法：将递归展开成树形结构，逐层求和
- 主定理 (Master Theorem)：对形如 T(n) = aT(n/b) + f(n) 的递推式有明确结论
链接到
- 上一个知识点：1.1 复杂度分析
- 下一个知识点：1.3 摊还分析概述