斐波那契数列的递归实现和非递归实现以及时间复杂度和空间复杂度分析
斐波那契数列是这样一个数列:1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765…表达式为:(注:斐波那契数列也可从n=0开始,对应的F(0)=0)递归和非递归代码实现:#include <iostream>using namespace std;//递归实现斐波那契数列int fib1(...
斐波那契数列是这样一个数列:1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765…
表达式为:
(注:斐波那契数列也可从n=0开始,对应的F(0)=0)
递归和非递归代码实现:
#include <iostream>
using namespace std;
//递归实现斐波那契数列
int fib1(int n)
{
if (n == 1 || n == 2)
return 1;
return fib1(n - 1) + fib1(n - 2);
}
//非递归实现斐波那契数列
int fib2(int n)
{
if (n == 1 || n == 2)
return 1;
int first = 1;
int second = 1;
int sum = 0;
while (n>2)
{
sum = first + second;
first = second;
second = sum;
n--;
}
return second;
}
int main()
{
cout << "递归实现斐波那契数列:" ;
for (int i = 1; i <= 20; i++)
{
cout << fib1(i) << " ";
}
cout << endl;
cout << "非递归实现斐波那契数列:" ;
for (int j = 1; j <= 20; j++)
{
cout << fib2(j) << " ";
}
}
运行结果:
时间复杂度和空间复杂度分析:
(1)递归实现
对于Fib(5)的递归过程可知,执行次数最多不超过但接近于二叉树最多时候的节点数,可近似看为
2
n
−
1
2^n-1
2n−1,所以时间复杂度T(n)为
2
n
2^n
2n的同阶,即
T
(
n
)
=
O
(
2
n
)
T(n)=O(2^n)
T(n)=O(2n)
在递归调用的过程中,除了存放程序本身所用的指令和变量,还需要另外开辟n个变量来作为辅助空间,分别对应Fib(n-1),Fib(n-2),Fib(n-3),…,Fib(0)中的n-1,n-2,n-3,…,0。因此,空间复杂度为
O
(
n
)
O(n)
O(n)。
(2)非递归实现
很显然,时间复杂度为
O
(
n
)
O(n)
O(n),空间复杂度为
O
(
1
)
O(1)
O(1)。
结语
如果你喜欢我写的文章,欢迎来踩我个人搭建的博客~
ChengNing’s Blog
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)