算法导论习题解答 4.2-4

amazingidiot

4.2-4利用递归树来找出递归式T(n)=T(n-a)+T(a)+cn的渐进紧确解，其中a>=1且c>0是常数。
解： 
                                              cn               cn 
                                c(n-a)          ca          cn
                    c(n-2a)       ca                       c(n-a) 
          c(n-3a)        ca                                c(n-2a)
………………………………………………           c(2a)
 
T(n)=cn+cn+c(n-a)+c(n-2a)+……c(2a) 
      =cn*n/a-(a+2a+…n-2a)
      =cn*n/a-2*(a+n-2a)*n/a
      =(c-2)*n2/a+n
      =Θ(n2)