解递归方程T(n)=2T(n^(1/2))+1并给出过程
时间: 2023-03-14 19:05:24 浏览: 358
答:解递归方程T(n)=2T(n^(1/2)),可以用递推关系法求解:T(n)=2T(n^(1/2))=2[2T(n^(1/4))]=2[2[2T(n^(1/8))]]=2[2[2[2T(n^(1/16))]]]=⋯=2^kT(n^(1/2^k)) (k为正整数)当上式右边的n^(1/2^k)取值为1时,T(n)=2^kT(1)即T(n)=2^k其中k=log2n,即T(n)=2log2n
相关问题
解递归方程T(n)=2T(n^(1/2))并给出过程
答: 根据递归公式可知,T(n) = 2T(n^(1/2)),可以把n代入幂函数n^(1/2),得T(n)=2T(n^(1/2))=2T(n^(1/4))=2^2T(n^(1/8))=2^3T(n^(1/16))=...=2^kT(n^(1/2^k)),当n^(1/2^k)=1时,即k=log2n,因此T(n)=2^log2n=2^(log2n),即T(n)=2^log2n。
解递归方程T(n)=2T(n^(1/2))+1,并给出过程
答:T(n) = 2^n * T(1),过程是:1. 首先令T(1) = c;2. 然后计算T(n) = 2T(n^(1/2)),即T(n) = 2 * 2T(n^(1/4));3. 继续计算T(n^(1/4)) = 2T(n^(1/8)),以此类推;4. 最后当n^(1/2^k) = 1时,即k = log2(n)时,T(n) = 2^log2(n) * c,即T(n) = 2^n * c。