文档章节

斐波那契数列递归实现和优化

cuibin1991
 cuibin1991
发布于 2016/08/16 09:57
字数 180
阅读 1
收藏 0

递归的求解过程存在严重的效率问题,如果想得到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

© 著作权归作者所有

共有 人打赏支持
cuibin1991
粉丝 2
博文 15
码字总数 2682
作品 0
房山
程序员
斐波那契查找(黄金分割法查找)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

serenity
2014/06/20
0
0
科普向 - 趣味的斐波那契数列

1.从一道面试题开始 每个程序员从第一次接触计算机编程语言到真正作为工程师进行项目开发,都一定都见过下面这道题目: 很多个台阶,可以一次走一个台阶,也可以一次走两个台阶,那么走台阶时...

ssssyoki
08/11
0
0
python实现斐波那契数列

斐波那契数列的发明者是意大利数学家昂纳多.斐波那契(Leonardo Fibonacci)。斐波那契数列又被称为黄金分割数列,或兔子数列。它指的是这样一个数列:0 1 1 2 3 5 8 13 21 34 ....在数学上,...

大陌
2017/07/09
0
0
重点汇总-python-gitbook-重要点学习-4-数据结构/编程题

数据结构 - 红黑树 红黑树与AVL的比较: AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多; 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;...

时间之友
2017/12/21
0
0
Common Lisp循环和递归

循环: 1)do循环 语法:(do ((变量名 变量初值 (变量变化语句))) (结束条件 返回值) 循环主体) CL-USER> (defun draw-line (x) (do ((i 0 (1+ i))) ((>= i x) nil) ;;nil可以忽略 (format ...

努力喵
2015/12/27
74
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

7 个致命的 Linux 命令

导读 如果你是一个 Linux 新手,在好奇心的驱使下,可能会去尝试从各个渠道获得的命令。以下是 7 个致命的 Linux 命令,轻则使你的数据造成丢失,重则使你的系统造成瘫痪,所以,你应当竭力避...

问题终结者
今天
0
0
设计模式:工厂方法模式(工厂模式)

工厂方法模式才是真正的工厂模式,前面讲到的静态工厂模式实际上不能说是一种真正意义上的设计模式,只是一种变成习惯。 工厂方法的类图: 这里面涉及到四个种类: 1、抽象产品: Product 2、...

京一
今天
0
0
区块链和数据库,技术到底有何区别?

关于数据库和区块链,总会有很多的困惑。区块链其实是一种数据库,因为他是数字账本,并且在区块的数据结构上存储信息。数据库中存储信息的结构被称为表格。但是,区块链是数据库,数据库可不...

HiBlock
今天
0
0
react native 开发碰到的问题

react-navigation v2 问题 问题: static navigationOptions = ({navigation, navigationOptions}) => ({ headerTitle: ( <Text style={{color:"#fff"}}>我的</Text> ), headerRight: ( <View......

罗培海
今天
0
0
Mac Docker安装流程

久仰Docker大名已久,于是今天趁着有空,尝试了一下Docker 先是从docker的官网上下载下来mac版本的docker安装包,安装很简易,就直接拖图标就好了。 https://www.docker.com/products/docker...

writeademo
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部