当前位置： 查字典图书网> 程序> 算法导论> 关于主定理的推导

关于主定理的推导

魏理布赫 对 算法导论 的书评 发表时间：2011-01-31 10:01:26


f(n)=a*f(n/b) + g(n)

f(n) 的结果在算法导论里面有很长的一段证明，作者可能照顾到一些没有学过组合数学的同学。然而，如果有组合数学的基础，这个证明非常简单。
只需要做一个变量替换，令 n=b^k，于是上式就变成：
 f(b^k) = a*f(b^(k-1)) + g(b^k) --->
 F(k) = a*F(k-1) + G(k)
 
这就是一个求解一个递归式的通项问题了，详细的我就不说了……

有用 3 无用 10

您对该书评有什么想说的？

对“关于主定理的推导”的回应

自由的角马
自由的角马 2013-04-01 23:14:29

递推式用生成函数

回应他
魏理布赫
魏理布赫 2012-05-04 17:44:23

看组合数学，里面有求解这类通项的详细描述

回应他
yycyycyy
yycyycyy 2012-04-12 10:34:43

思路可以，但是求解F(k) = a*F(k-1) + G(k) 的通项不容易啊。。

回应他

《算法导论》热门书评

算法导论

书名： 算法导论
作者： [美] Thomas H·Cormen
出版社： 高等教育出版社
出版年： 2002-5
页数： 1180
定价： 68.00元
装帧： 平装
丛书： 国外优秀信息科学与技术系列教学用书
ISBN： 9787040110500