斐波那契算法是最常見的遞歸算法肺然，簡單版本的代碼如下：
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)，重復(fù)運算太多了芒珠。下面則是一個時間復(fù)雜度為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;
}
利用時間函數(shù)可以對比二者時間差距牺堰，前者完全沒法看拄轻，第二種算法則是非常快速伟葫，下面是完整的代碼：
#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;
}