斐波拉契数是一个很经典的问题,也会很多公司面试的考题,每个学习计算机的同学都会接触这个问题,尤其是在学习递归的时候,利用递归来解决斐波拉契数是很多教材采用的一个例子,所以很多同学一想到斐波拉契马上就会采用递归,递归貌似简单,但是效率真的很高吗?不然!下面是我在学习动态规划的过程中总结的集中解决斐波拉契数的不同方法:
一、最野蛮最原始的方法
这是最直接的递归方式,其时间复杂度为O(1.618^n),是一个指数时间级的算法,当n超过30时,你就慢慢等待吧,运气差的话直接死机了。
二、自底向上的动态规划方法
我们已知F(0)和F(1)的值,则我们从F(2)开始就可以利用前面两个已经计算出来的值,这样从小到大就可以最终求出F(n)
其时间复杂度已经从指数级降到线性级O(n)了,空间复杂度为O(1)
三、自顶向下的动态规划方法
这种方法也是采用递归的思想,但是确应用了动态规划的原理:将以前的计算结果存储起来备用,这样在以后出现同样的问题时就不用重复计算。也叫备忘录方法。
自顶向下的动态规划递归方法大大减少了递归调用的次数,避免了重复递归计算,其算法时间复杂度也为线性级,其关键就是能够"保存已经计算过的子问题的结果".
分享到:
相关推荐
斐波拉契数列线性代数安阳工学院PPT学习教案.pptx
斐波拉契数列在股市中的运用.pdf
斐波拉契数列在股市中的运用.doc
斐波拉契数列用分治法实现算法,整体效率比用递归方式实现要快出很多。我已经亲手测试过了,希望上传的资源可以帮到大家。如果有任何问题要记得给我留言,大家一起探讨,共同进步啊。
NULL 博文链接:https://hongan.iteye.com/blog/309766
android Handler子线程计算斐波那契数列
非递归的,利用一个数组解决的斐波拉契问题解法,简洁明了,新手教学
在Hash查找方法中 散列函数构造方法多种多样 同时对于同一散列函数解决冲突的方法也可以不同 两者是影响查询算法性能的关键因素 对于几种典型的散列函数构造方法 做实验观察 不同的解决冲突方法对查询性能的影响 ...
利用递归的算法解斐波拉契数列问题,新手学习用
斐波拉契汇编语言的官方提供版本。MARS
汇编语言实现斐波拉契数列,可支持输入的最大数字为24
本文实例讲述了Python打印斐波拉契数列的方法。分享给大家供大家参考。具体实现方法如下: #打印斐波拉契数列 #!/usr/bin/python def feibolaqi(n): if n == 0 or n == 1: return n else: return feibolaqi(n-1...
斐波拉契数列前900项。
用C语言输出斐波拉契数列的前五十项。。。。。。。
MIPS程序-斐波拉契数列
200以内的水仙花数,2-n之间的质数,前n项的斐波拉契数列,三项功能集合为一种!
使用c语言写一个斐波拉契数列,使用该程序可以直接过航电acm的那道关于斐波拉契数列的题,这是作者写了一天的成果