最早研究这个数列的当然是斐波那契喽。他当时是为了描述如下的兔子增长数目。
后来被广泛应用于各种场合，这是数列的定义如下：
首先呢，当我们看到这个数列时，想到的先是用递归的方法实现：
也可用三目运算符实现：
分析：
递归的时间复杂度：递归的次数*每次递归次数。
递归的空间复杂度：递归深度*每次递归的大小。
运用递归实现斐波那契数列，效率非常低。
时间复杂度为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，防止越界。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
计算
安全
数据库
网络和加速
企业服务
