如何用生成函数求解递归方程f(n)=2f(n/2)+cn
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
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
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
Sievers分析仪
2025-02-09 广告
是的。传统上，对于符合要求的内毒素检测，最终用户必须从标准内毒素库存瓶中构建至少一式两份三点标准曲线；必须有重复的阴性控制；每个样品和PPC必须一式两份。有了Sievers Eclipse内毒素检测仪，这些步骤可以通过使用预嵌入的内毒素标准...
点击进入详情页
本回答由Sievers分析仪提供
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
