Fibonacci數(shù)列算法的幾種實現(xiàn)方式與比較

2019-11-06 06:31:56

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

斐波那契數(shù)列1，1，2，3，5，8…，對于該數(shù)列的求解又如下幾種方式。

version1

//version1int Fibonacci(int n,int* f){ f[0]=1; f[1]=1; for(int i=2;i<n;i++) f[n]=f[n-1]+f[n-2]; return f[n-1]; }

分析：輸入?yún)?shù)是一個存儲斐波那契數(shù)列的數(shù)組，返回第n個數(shù)的值。該算法運用動態(tài)規(guī)劃，將所有的斐波那契數(shù)計算并存儲在數(shù)組中，使得各個數(shù)不需要重復(fù)計算。時間復(fù)雜度為O(n),空間復(fù)雜度為數(shù)組n的大小。

version2

//version2int Fibonacci(int n){if(n==1) return 1;if(n==2） int f_twoback=1; int f_oneback=1; int f; for(int i=2;i<n;i++) { f=f_twoback+f_oneback; twoback=f_oneback; f_oneback=f; } return f; }

分析：有時候我們只需要斐波那契數(shù)列的其中某個位置的數(shù)，并不需要所有的數(shù)列，所以我們可以用2個變量來存儲其兩個加數(shù)，從而并不需要數(shù)組的存儲，并能夠節(jié)省空間。算法的時間復(fù)雜度還是同version1.

version3

//version3 int fibonacci(int n){ if(n==1) return 1; if(n==2) return 2; return fibonacci(n-1)+fibonacci(n-2);}

分析：該算法是遞歸版本，雖然結(jié)構(gòu)簡單，但是復(fù)雜度很高，效率低下。

version4

//version4memorized_fibonacci_recurs(int* results,int n){ if(results[n]!=-1) return results[n]; if(n==1) val=1; else if(n==2) val=1; else { val=memorized_fibonacci_recurs(results,n-2); val+=memorized_fibonacci_recurs(results,n-1); } results[n]=val; return val;}int memorized_fibonacci(int n){ return memorized_fibonacci_recurs(results.n);}