斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci[1]）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。
  指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：  
      F（0）=0，F(xiàn)（1）=1，F(xiàn)（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
  
  
#include<iostream>
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];
	}
}
//優(yōu)化    時(shí)間復(fù)雜度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適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書合作）期待與您的合作！

我們不難發(fā)現(xiàn)在這棵樹中有很多結(jié)點(diǎn)會(huì)重復(fù)的，而且重復(fù)的結(jié)點(diǎn)數(shù)會(huì)隨著n的增大而急劇增加。這意味這計(jì)算量會(huì)隨著n的增大而急劇增大。事實(shí)上，用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以n的指數(shù)的方式遞增的.

     在分析算法的時(shí)間復(fù)雜度的時(shí)候，我們也可以得到相同的結(jié)果，非遞歸使用的是for循環(huán)，其時(shí)間復(fù)雜度為O(n)。而遞歸的時(shí)間復(fù)雜度則比較復(fù)雜，其分析出來為O(2^n)。

     這里需要說明的就是，非遞歸的for循環(huán)其時(shí)間復(fù)雜度O(n)雖然很小，但是其空間復(fù)雜度缺比遞歸調(diào)用差得多。因?yàn)?，for循環(huán)在每次循環(huán)的時(shí)候，都把相應(yīng)的數(shù)值保存下來了，而遞歸調(diào)用卻不會(huì)保存相應(yīng)的數(shù)值。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

當(dāng)前文章：斐波那契序列的遞歸和非遞歸的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://jinyejixie.com/article26/ccjhjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、定制開發(fā)、軟件開發(fā)、靜態(tài)網(wǎng)站、網(wǎng)站營(yíng)銷、網(wǎng)站排名

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)