斐波那契数列的四种实现方式

云计算 waitig 563℃ 百度已收录 0评论

首先来介绍一下斐波那契数列:

        斐波那契数列(Fibonacci sequence),又称黄金分割数列。因数学家列昂纳多·斐波那契(Leonardoda
Fibonacci)以兔子繁殖为例子而引入,故又称为“
兔子数列”。指的是这样一个数列:1、1、2、3、5、8、13、21、34、……

        从定义可以看出斐波那契数列就是第一二项都是1,从第三项开始,每一项为前两项之和。那么要想知道每一项,只要知道前两项就可以得到了,前两项怎么得到?根据这同一种套路,直到前两项分别为第一二项(都是1),所有的不就都解决了。既然这样,很容易的就想到可以利用递归的方式去实现它了。

方法一:递归实现

这种方式虽然可以实现,而且代码也是很简单,但是很遗憾的是,它有一个很大的缺陷。就以求第5项为例子来分析一下:

       通过上图可以看到,当求F(5)时,需要递归调用很多次,关键是其中有时候做的事情还是完全一样的,比如F(3)求了两次。当求得不是第5项而是更大的项,那么重复的会更多。我们都知道调用函数的开销是很大的,而该种方法就是在不断地调用同一个函数还做着许多无用功,它的时间复杂度高达O(2^n),可见它的效率是很低的。

        方法1是由需要求的那一项倒着会去求,然后在依次返回,从而导致做了很多无用功,那么,如果从第一项开始,从前依次往后求,直到将需要求的那项求出来,这样就不会有重复求某一项的事情发生了,效率相对也就高一些了。


方法二:递归进阶版

这种方法相对方法1来说,其时间复杂度为O(N),空间复杂度为O(1),效率稍微要高一点,但可能不太好理解。可以将它的调用过程画出来帮助理解。

既然可以使用递归,那么毫无疑问,也是可以使用循环来实现的。

方法三:

这种方法的时间复杂度为O(N),空间复杂度为O(1),很简单,在这里就不多做解释了。


方法四:

利用数组将斐波那契数列的元素存起来,一般用于求斐波那契数列的前N项

方法四的时间复杂度为O(N),空间复杂度为O(1),是一种效率比较高的方法。

关于斐波那契数列就讲到这里,欢迎大家提出表柜意见哦~


本文由【waitig】发表在等英博客
本文固定链接:斐波那契数列的四种实现方式
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)