Question

如何用生成函数求解递归方程f(n)=2f(n/2)+cn

Answer 1

^对于形式如f(n)=g(n)f(n-1)+h(n)的递归方程，可利用递推关系得到：
f(n)=g(n)f(n-1)+h(n)
=g(n)g(n-1)g(n-2)....g(1)g(0)[f(0)+
sum[
h(i)/g(i)g(i-1)...g(1)]
]。其中，sum表示i从1到n求和。
对上面的式子，可以设n=2^k，则k=logn。则有：
f(k)=2f(k-1)+c2^k
直接应用公式，得：
f(k)=2^k[
c*sum(2^i/2^i)
]
=2^k*c*k
=cnlogn