首页 > 其他 > 详细

趣谈斐波那契数列

时间:2016-04-10 01:29:35      阅读:525      评论:0      收藏:0      [点我收藏+]

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

技术分享

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

技术分享


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

技术分享


也可用三目运算符实现:

技术分享


分析:

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

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


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

时间复杂度为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,防止越界。

本文出自 “一起去看星星” 博客,转载请与作者联系!

趣谈斐波那契数列

原文:http://10810429.blog.51cto.com/10800429/1762109

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!