算法导论习题解答 4.2-4

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)

?