企业网站制作服务,wordpress 后台被锁定,公司品牌网站设计,视频推广方案模板当前面所学习的迭代法、差消法等不太好解决的问题#xff0c;可以使用递归树#xff0c;来很方便的解决。 文章目录1. 递归树的概念1.1 迭代在递归树中的表示2. 递归树的生成规则2.1 递归树生成实例2.2 递归树应用实例3. 总结1. 递归树的概念
递归树是迭代计算的模型递归树的… 当前面所学习的迭代法、差消法等不太好解决的问题可以使用递归树来很方便的解决。 文章目录1. 递归树的概念1.1 迭代在递归树中的表示2. 递归树的生成规则2.1 递归树生成实例2.2 递归树应用实例3. 总结1. 递归树的概念
递归树是迭代计算的模型递归树的生成过程与迭代过程一致递归树上的所有项恰好是迭代之后产生的和式中的项对递归树上的项求和就是迭代后方程的解
1.1 迭代在递归树中的表示
如果递归树上某节点记为W(m),则
举个例子二分归并排序的时间复杂度的递推式子对应的递归树为 2. 递归树的生成规则
初始递归树只有根节点其值为W(n)不断继续下述过程
将函数项叶节点的迭代式W(m)表示成二层子树用该子树替换该叶节点
继续递归树的生成直到树种无函数项只有初值为止
2.1 递归树生成实例
下面还是以二分归并的例子来说明递归树的生成过程 最终形成递归树 然后对上面递归树每个节点相加进行求和即可得到W(n)的值
这与前面求得的结果一样。
2.2 递归树应用实例
求解 它的递归树为 观察上面的递归树每一行的和都是n。但是因为左边子树短一些右边子树长一些所以最终的极限末尾处左边已经没有节点但是右边还有节点但是此时右边的节点和不会超过n所以取其极限O(n).
然后对上面的式子进行求和 可以看出利用递归树可以很容易的求出上述的结果但是利用迭代就比较麻烦。
3. 总结
递归树是迭代的图形表示学会递归树的生成规则学会使用递归树求解递推方程的解
