趣谈斐波那契数列-创新互联

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

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

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

也可用三目运算符实现：

分析：

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

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

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

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

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。