算法导论学习笔记——第4章
浏览数：18 /
时间：2015年06月08日
解递归式
1、代换法substitution
1）猜测解的形式
2）用数学归纳法找出使解真正有效的常数
2、递归树
使用递归树时，可以忽略一些“小误差”，将递归产生的结果作为猜测，用代换法进行验证。
也可以严格计算每一层递归树的代价，加总成递归式的结果。
对于有两个子问题，子问题规模为1/2的递归树（二叉树），树的高度是lgn，叶级节点的数量是n
3、主方法master method
递归式形式T(n)=aT(n/b)+f(n)，其中a>=1，保证有一个及以上子问题；b>1，保证问题的规模逐步变小，否则问题会趋向于无穷；f(n)渐进趋正。
从极限的角度比较aT(n/b)和f(n)，更高阶的一项决定递归式的解
1）aT(n/b)比f(n)高阶，T(n)=Θ(nlogba)
2）aT(n/b)与f(n)同阶，T(n)=Θ(nlogbalgn)
3）aT(n/b)比f(n)低阶，T(n)=Θ(f(n))
并非所有的递归式都能应用这三种情况。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
