求解递归方程两个,假定n为2的方幂.

求解递归方程两个,假定n为2的方幂.

题目
求解递归方程两个,假定n为2的方幂.
不要求非常详细,有必要的几个步骤就可以了
1、T(n)=4*T(n/2)+n
2、T(n)=4*T(n/2)+n^2
两个差不多,答对有高分相送,急.
答案
前一个:
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)可取任意常数
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点

超级试练试题库

© 2017-2019 超级试练试题库,All Rights Reserved.