成都网站建设设计

将想法与焦点和您一起共享

斐波那契序列的递归和非递归的实现-创新互联

  斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1])以兔子繁殖为例子而引入,故又称为“兔子数列”。
  指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:  
      F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)
  
  
#include
using namespace std;
//递归形式
//long long  fibonacci(int i)
//{
//	return i < 2 ? i : fibonacci(i - 1) + fibonacci(i - 2);
//}
void test1()
{
	cout << fibonacci(6) << endl;;
}
//非递归形式
long long fibonacci(int n)
{
	int tem[2];
	tem[0] = 1;
	tem[1] = 1;
	if (n == 0)
	{
		return 0;
	}
	if ( n == 1)
	{
		return 1;
	}
	else
	{
		for (int i = 2; i < n; i++)
		{
			int temp = tem[0] + tem[1];
			tem[1] = tem[0];
			tem[0] = temp;
		}
		return tem[0];
	}
}
//优化    时间复杂度O(n)
long long fibonacci(int n)
{
	long long fibonacci[3] = { 0, 1, n };
	for (int i = 2; i <= n; ++i)
	{
		fibonacci[2] = fibonacci[1]+fibonacci[0];
		fibonacci[0] = fibonacci[1];
		fibonacci[1] = fibonacci[2];
	}
	return fibonacci[2];
}
int main()
{
	test1();
	system("pause");
	return 0;
}

   斐波那契序列的递归和非递归的实现

呈贡ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18980820575(备注:SSL证书合作)期待与您的合作!

斐波那契序列的递归和非递归的实现

我们不难发现在这棵树中有很多结点会重复的,而且重复的结点数会随着n的增大而急剧增加。这意味这计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的.

斐波那契序列的递归和非递归的实现

     在分析算法的时间复杂度的时候,我们也可以得到相同的结果,非递归使用的是for循环,其时间复杂度为O(n)。而递归的时间复杂度则比较复杂,其分析出来为O(2^n)。

     这里需要说明的就是,非递归的for循环其时间复杂度O(n)虽然很小,但是其空间复杂度缺比递归调用差得多。因为,for循环在每次循环的时候,都把相应的数值保存下来了,而递归调用却不会保存相应的数值。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


新闻名称:斐波那契序列的递归和非递归的实现-创新互联
文章分享:http://chengdu.cdxwcx.cn/article/ccjhjg.html