算法设计与分析题目

题目

算法设计与分析题目
递归方程 f(n)=4f(n/2)+n f(1)=1 其中,n是2的幂 用递推法解此方程

答案

设n=2^k,把原式变形为f(2^k)/4^k=f(2^(k-1))/4^(k-1)+0.5^k,令a(k)=f(2^k)/4^k,得a(k)=a(k-1)+0.5^k (a(0)=1),a(k)=2-0.5^k,f(n)=2n^2-n