Question

求解递归方程

求解递归方程两个，假定n为2的方幂。

不要求非常详细，有必要的几个步骤就可以了

1、T(n)=4*T(n/2)+n
2、T(n)=4*T(n/2)+n^2

两个差不多，答对有高分相送，谢谢。急。

Answer 1

前一个：
T(n)=4T(n/2)+n可以等价地写成T(2^t)=4T(2^(t-1))+2^t，
所以
T(2^t)+2^t=4T(2^(t-1))+2*2^t=4T(2^(t-1))+4*2^(t-1)=4[T(2^(t-1))+2^(t-1)]，
令R(t)=T(2^t)+2^t，则上式说明R(t)=4R(t-1)。所以
R(t)=4R(t-1)=(4^2)R(t-2)=...=(4^t)R(0)，
所以
T(2^t)=R(t)-2^t=(4^t)R(0)-2^t=(4^t)[T(2^0)+2^0]-2^t=(4^t)[T(1)+1]-2^t=(4^t)T(1)+4^t-2^t，
或者写成
T(n)=(n^2)T(1)+n^2-n，
其中T(1)可取任意常数

后一个：
T(n)=4T(n/2)+n^2可以等价地写成T(2^t)=4T(2^(t-1))+4^t，
所以
T(2^t)-t*4^t=4T(2^(t-1))+4^t-t*4^t=4T(2^(t-1))-(t-1)*4^t=4[T(2^(t-1))-(t-1)*4^(t-1)]，
令R(t)=T(2^t)-t*4^t，则上式说明R(t)=4R(t-1)。所以
R(t)=4R(t-1)=(4^2)R(t-2)=...=(4^t)R(0)，
所以
T(2^t)=R(t)+t*4^t=(4^t)R(0)+t*4^t=(4^t)[T(2^0)-0*2^0]+t*4^t=(4^t)T(1)+t*4^t，
或者写成
T(n)=(n^2)T(1)+(n^2)ln(n)/ln(2)，
其中T(1)可取任意常数