斐波那契序列以及优化

斐波那契序列的实现和优化

• 最简单的实现

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 最近我在学大话数据结构这块看到了斐波那契序列查找。看了原文加了自己的理解