斐波那契数列递归实现和优化
斐波那契数列递归实现和优化
cuibin1991 发表于1年前
斐波那契数列递归实现和优化
  • 发表于 1年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

递归的求解过程存在严重的效率问题,如果想得到f(10),需要先求解f(8)和f(9)。而求解f(9)又要先求解f(8)和f(7),如书中的树形结构:

输入图片说明

树中有很多重复节点,重复节点会随着n的增大而急剧增加,计算量也会随着n增大而急剧增大。

优化:从上往下计算,首先根据f(0)和f(1)算出f(2),再关键f(1)和f(2)算出f(3).....依次算法第n项。这种思路的时间复杂度是O(n)。

递归和优化的代码实现如下:http://www.oschina.net/code/snippet_1051716_58660

标签: 斐波那契
共有 人打赏支持
粉丝 3
博文 15
码字总数 2682
×
cuibin1991
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: