目录
一、特征方程
2.1 线性齐次递推式的求解
2.1.1 对于一阶齐次递推关系
2.1.2 对于二阶齐次递推关系
2.2 非齐次递推式的求解
2.2.1 常用的非齐次递推式的求解1(ing)
2.2.2 常用的非齐次递推式的求解2(ing)
二、递归树
三、主方法
3.1 主定理
3.2 应用实例
一、特征方程
2.1 线性齐次递推式的求解
用来代替该等式中的，则，
所以有：
两边同时除以得到：
或者写成： ，此为特征方程，
可以求出特征方程的根，如果该特征方程的k个根互不相同，令其为r1、r2、…、rk，
则得到递归方程的通解为：
再利用递归方程的初始条件（)确定通解中的待定系数
从而得到递归方程的解。
2.1.1 对于一阶齐次递推关系
如，假定序列从开始，且，可以直接递推求解，即：
2.1.2 对于二阶齐次递推关系
如，假定序列从开始，且
其特征方程为
令这个二次方式的根是和，可以求解递推式的解是：
代入 求出和
例题：分析求解Fibonacci数列的递归算法的时间复杂度
2.2 非齐次递推式的求解
其通解形式如下：
其中，是对应齐次递归方程的通解，是原非齐次递归方程的特解。
现在还没有一种寻找特解的有效方法。一般是根据g(n)的形式来确定特解:
假设g(n)是n的m次多项式，即
则特解
代入原递归方程求出、、…、。
再代入初始条件（) 求出系数得到最终通解。
2.2.1 常用的非齐次递推式的求解1(ing)
2.2.2 常用的非齐次递推式的求解2(ing)
二、递归树
用递归树求解递归方程的基本过程是：
（1）展开递归方程，构造对应的递归树。
（2）把每一层的时间进行求和，从而得到算法时间复杂度的估计。
三、主方法
主方法（master method）提供了解如下形式递归方程的一般方法：
其中a≥1，b>1为常数
该方程描述了算法的执行时间，算法将规模为n的问题分解成a个子问题，每个子问题的大小为n/b。例如，对于递归方程，有：
3.1 主定理
应用该定理的过程是，首先把函数f(n)与函数进行比较，递归方程的解由这两个函数中较大的一个决定：文章来源：https://www.toymoban.com/news/detail-483524.html
- 情况（1），函数比函数f(n)更大，则 。
- 情况（2），函数和函数f(n)一样大，则 。
- 情况（3），函数比函数f(n)小，则。
3.2 应用实例
文章来源地址https://www.toymoban.com/news/detail-483524.html
到了这里，关于算法学习 | 递归方程求解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
