斐波那契数列的两种算法

斐波那契算法是最常见的递归算法，简单版本的代码如下：

long long fib(int n){
    if(n <= 0)  return 0;
    if(n == 1)  return 1;
    return fib(n-1) + fib(n-2);
}

但显然这个算法的效率极低，因为在计算fib(n)和fib(n+1)的时候都会运算fib(n-2)，重复运算太多了。下面则是一个时间复杂度为o(n)的效率较高的算法：

long long fib(int n){
    if(n <= 0)  return 0;
    if(n == 1)  return 1;
    long long fib1 = 0;
    long long fib2 = 1;
    long long fibN = 0;
    for(int i = 2; i <= n; i++){
        fibN = fib1 + fib2;
        fib1 = fib2;
        fib2 = fibN;
    }
    return fibN;
}

利用时间函数可以对比二者时间差距，前者完全没法看，第二种算法则是非常快速，下面是完整的代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>  

long long fib(int n){
    if(n <= 0)  return 0;
    if(n == 1)  return 1;
    long long fib1 = 0;
    long long fib2 = 1;
    long long fibN = 0;
    int i;
    for(i = 2; i <= n; i++){
        fibN = fib1 + fib2;
        fib1 = fib2;
        fib2 = fibN;
    }
    return fibN;
}
int main()
{
    clock_t start,finish;
    int i;
    start = clock();
    for(i = 0; i < 1000; i++){
        printf("%lld ",fib(i));
    }
    finish = clock();
    double runtime = (double)(finish-start);
    printf("%runtime:%lf", runtime);
    return 0;
}