递归树方法

1.递归树方法是以树的形式表示迭代方法的图形表示, 其中在每个级别上扩展节点。

2.通常, 我们将复发的第二项视为根。

3.当使用分而治之算法时, 这很有用。

4.有时很难提出一个很好的猜测。在递归树中, 每个根和子节点代表单个子问题的成本。

5.我们对树的每个级别内的成本求和, 以获得一组预级别成本, 然后对所有预级别成本求和以确定递归所有级别的总成本。

6.最好使用递归树来生成良好的猜测, 可以通过替代方法进行验证。

例子1

Consider T (n) = 2T + n2

我们必须使用递归树方法获得渐近界。

解决方案:上述重复的递归树是

DAA递归树方法
DAA递归树方法

示例2:考虑以下重复

T (n) = 4T +n

使用递归树方法获得渐近边界。

解决方案:以上递归的递归树

DAA递归树方法
DAA递归树方法

示例3:考虑以下重复

DAA递归树方法

使用递归树方法获得渐近边界。

解决方案:给定的递归具有以下递归树

DAA递归树方法

当我们在递归树的各个级别上添加值时, 每个级别的值都为n。从根到叶的最长路径是

DAA递归树方法

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?