现在的位置: 首页 > 综合 > 正文

递归树

2018年02月09日 ⁄ 综合 ⁄ 共 488字 ⁄ 字号 评论关闭

递归树

   
递归树的结点有两个域,如下图:

    T(size)指问题大小为size时,函数的复杂度。nonrec.cost指问题大小为size时的非递归代价。

    
根结点的每个子结点都代表了这个问题分拆的一个子问题的复杂度。就这样递归地分解问题。一直到达叶子结点,也就是base-case.在前面的讨论中,我们没有涉及base-case,在使用递归树分析复杂度时,我们假设base-case的复杂度为1

    
举一个例子就可以很明白的说明如何构造递归树。

Example1:     由递归方程T(n)=2T(n/2)+n构造递归树

    
首先,构造根接点

它的子结点是

     ……,以此类推。所以,最后的递归树为:

递归树规则:

    
根结点的复杂度=所有非叶结点的非递归复杂度+叶子结点的复杂度。

所以,在上面的例子中,每层的非递归复杂度为n,base-case出现在大约lgn(n/2^d
=1;d = lgn)
。由于base-case的复杂度为1,所以T(n)nlgn,即

    
递归树是分析和计算递归方程的一个重要工具。它可以直观地表示出递归函数的复杂度,并使人易于理解。

抱歉!评论已关闭.