Fibonacci数列算法的几种实现方式与比较

2019-11-06 06:31:56

字体：大中小

来源：转载

供稿：网友

斐波那契数列1，1，2，3，5，8…，对于该数列的求解又如下几种方式。

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]; }

分析：输入参数是一个存储斐波那契数列的数组，返回第n个数的值。该算法运用动态规划，将所有的斐波那契数计算并存储在数组中，使得各个数不需要重复计算。时间复杂度为O(n),空间复杂度为数组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; }

分析：有时候我们只需要斐波那契数列的其中某个位置的数，并不需要所有的数列，所以我们可以用2个变量来存储其两个加数，从而并不需要数组的存储，并能够节省空间。算法的时间复杂度还是同version1.

version3

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

分析：该算法是递归版本，虽然结构简单，但是复杂度很高，效率低下。

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);}