斐波那契数列是这样一个数列: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 2n1,所以时间复杂度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

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐