题目

求解递归方程两个,假定n为2的方幂.
不要求非常详细,有必要的几个步骤就可以了
1、T(n)=4*T(n/2)+n
2、T(n)=4*T(n/2)+n^2
两个差不多,答对有高分相送,急.

提问时间：2021-03-15

答案

前一个：
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)可取任意常数