趣谈斐波那契数列

发布时间:2020-08-16 22:38:29 作者:下一个明天
来源:网络 阅读:541

   最早研究这个数列的当然是斐波那契喽。他当时是为了描述如下的兔子增长数目。

趣谈斐波那契数列

后来被广泛应用于各种场合,这是数列的定义如下:

趣谈斐波那契数列


  首先呢,当我们看到这个数列时,想到的先是用递归的方法实现:

趣谈斐波那契数列


也可用三目运算符实现:

趣谈斐波那契数列


分析:

递归的时间复杂度:递归的次数*每次递归次数。

递归的空间复杂度:递归深度*每次递归的大小。


运用递归实现斐波那契数列,效率非常低。

时间复杂度为O(2^n),空间复杂度为O(n)。


斐波那契数列的优化:


斐波那契数列:0,1,1,2,3,5,8...

可得出规律:从第三个数开始,每个数都为前两个数之和。

趣谈斐波那契数列

注:时间复杂度为O(n),空间复杂度为O(1)


也可用数组的方式实现:

趣谈斐波那契数列

注:时间复杂的为O(n),空间复杂度为O(n)。


注意:

(1)在斐波那契数列中,一定注意当n=0时,结果为0。

(2)应用long long,防止越界。

推荐阅读:
  1. 关于“斐波那契数列”的编程
  2. 【C++】 斐波那契数列

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

斐波那 契数列 契数

上一篇:Oracle常见死锁发生的原因以及解决方法

下一篇:回馈开源,我如何排查一个MySQL Bug

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》