首先基础的递归算法
#include <stdio.h>#include <string.h>#include <windows.h>#include <iostream>DWORD time_start, time_end;int book[1001];int fac(int i){if ((i == 1) || (i == 2))return 1;if (i > 2) {return fac(i-1) + fac(i-2);}return 0;}int main(){int i = 0;int n;std::cin >> n;memset(book, 0, sizeof(book));time_start = GetTickCount();for (i = 1; i < n; i++){printf("%d ",fac(i));}printf("\n");time_end = GetTickCount();std::cout << "TIME = " << (time_end - time_start) << "ms" << std::endl;return 0;}
这是运行的记录，时间已经达到了7秒左右
最后两个数已经很慢了
这个递归是爆炸增量函数，属于指数级函数，膨胀迅速。
我们看看n=46的时候
只是n+1，就加了5秒，因为最后一个数要执行前面的数的所有步骤，所以这个方法只是在n=3~50的范围。
上图是我用matplotlib做的函数曲线图，蓝色线就是爆炸增量函数，增长最快了。
因为每新增一个数，就会成倍的执行前面的所有步骤。所以我们要剪掉重复步骤，记录每一次结果。如下：
#include <stdio.h>#include <string.h>#include <windows.h>#include <iostream>using namespace std;DWORD time_start, time_end;int fb[1000];int fac(int i){if (fb[i]>0)return fb[i];if ((i == 1) || (i == 2)) {fb[i]=1;return 1;}if (i > 2) {int a= fac(i-1) + fac(i-2);fb[i]= a;return a;}}int main(){int i = 0;int n;std::cin >> n;time_start = GetTickCount();for (i = 1; i < n; i++){printf("%d ",fac(i));}printf("\n");time_end = GetTickCount();std::cout << "TIME = " << (time_end - time_start) << "ms" << std::endl;return 0;}
比循环的速度还要快，循环是线性的复杂度，不需要回调。
上图是循环实现
#include <iostream>#include <windows.h>using namespace std;DWORD time_start, time_end;int main(){int a[1001], n;time_start = GetTickCount();cin >> n;a[0] = 1;a[1] = 1;for (int i = 2; i < n; i++){a[i] = a[i - 1] + a[i - 2];cout << a[i] << " ";} cout << endl;time_end = GetTickCount();cout << "Time = " << (time_end - time_start) << "ms\n ";return 0;}
