斐波那契序列的实现和优化
- 最简单的实现
int fibSum(int n){
if (n==0) {
return 0;
}
if (n==1||n==2) {
return 1;
}
return fibSum(n-2) + fibSum(n-1);
}
这是最基本的递归思路，大家的第一个斐波那契数列应该都是写成这样的。但是这样写的性能很差，当N为几十几的时候，计算机就承载不住了。N为45的时候测试用例的时间周期就使用了145s。
- 第一层优化，计算出递归的结果后通过数组存储起来，避免后面的元素再次将重复的数据递归
long fibSum4(long n){
static long*arr = new long[n+1]();
if (n==0) {
return 0;
}else if (n==1){
return 1;
}else if (n>1){
if (arr[n]!=0) {
return arr[n];
}else{
arr[n] = fibSum4(n-2) + fibSum4(n-1);
return arr[n];
}
}
return 0;
}
这样处理的结果后效率明显提高，N为1000的时候。耗时还是将近0s,但是当N将近5000的时候还是出现的栈溢出，栈溢出的本质原因是开辟的大量的临时存储空间发生了栈溢出。真正要解决这个问题 要么使用尾递归，要么使用循环代替递归。
- 第二层优化
long Fibonaccics(long n){
long*temp = new long[n+1];
temp[0] = 0;
if (n==1) {
temp[n] = 1;
}
for (int i = 2; i<=n;i++) {
temp[i] = temp[i-1] + temp[i-2];
}
long result = temp[n];
delete[] temp;
return result;
}
现在，当N=1000000的时候，时间仍然小于1秒了。 时间复杂度为O(n)。
注：原文链接http://blog.csdn.net/woshisap/article/details/7566946 最近我在学大话数据结构这块看到了斐波那契序列查找。看了原文加了自己的理解
