解递归方程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。

相关问题

解递归方程T(n)=2T(n^(1/2))+1并给出过程

答：解递归方程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。