skip to main
|
skip to sidebar
Zheng-Yu 的博墅网志
走进我的学习、工作和生活
2007年2月26日星期一
Fibonacci数列之转移矩阵法
Fibonacci数列:
在讲递归和递推时都是经典例题,一般都是递归(O(2^n)),递推(O(n)),也有用通项公式法
看上去是O(1),其实不然,我们还应该考虑乘方运算的时间消耗。如不加特别优化,用乘法实现n次乘方的时间复杂度为O(n)。
但是上帝跟我说了一种非常规的算法——转移矩阵法!
这个矩阵的n次方就是
,即Fibonacci数列的第n项!
如求F5:
然后二分一下,复杂度就变成O(lgn)了!
1 条评论:
Unknown
说...
看不懂啊,下次出点容易点的哦
2007年2月26日 21:17:00
发表评论
较新的博文
较早的博文
主页
订阅:
博文评论 (Atom)
输入您的搜索字词
提交搜索表单
Web
alfantastic.blogspot.com
我的简介
Zheng-Yu Chen
查看我的完整个人资料
Friends blog
神的傢園
┟飛鳥ˇ’夢〃
๑۩۩ 不会太远☆๑۩۞۩$
๑梦呓★溺爱★颠覆๑
上帝是骑士
Qz.月怡少侠
Qz.能能
闪光的树
Useful Link
Linux基本命令
USACO Translate
USACO
Google Office *new
Favorites
明朝遗憾:本应世界最早宪政资本主义强国
博客归档
►
2008
(1)
►
十一月
(1)
▼
2007
(37)
►
十一月
(1)
►
七月
(1)
►
六月
(2)
►
五月
(5)
►
四月
(3)
►
三月
(11)
▼
二月
(14)
WOW,Ubuntu!
开学啦
Google与金山词霸合作 fy updating now!
Google大预言
但愿Gates没看见,要出人命的!
the last night of the Winter-holiday
Fibonacci数列之转移矩阵法
发现中美撞机录象
论年味
强爆(反了)!!Telnet字符版星球大战
挤公交
添加访问统计
Ajax
开张公告
1 条评论:
看不懂啊,下次出点容易点的哦
发表评论