最近在网课学习中
了解了一些基本算法
其中在递归算法时
在无优化递归斐波那契时
程序效率低
因为许多数在之前已经被算过一遍了
所以使用记忆化搜索优化
#include<iostream> #include<cstring> #include<Windows.h> using namespace std; int flog(int v); int s[1000]; int main() { int n,k; cin>>n; DWORD startTime=GetTickCount(); k=flog(n); DWORD endTime=GetTickCount(); cout<<k<<" "<<endTime-startTime; } int flog(int v) { if(v==1) return 0; if(v==2) return 1; if(s[v]==0) s[v]=flog(v-1)+flog(v-2); return s[v]; }
对比不经过优化的
#include<iostream> #include<Windows.h> using namespace std; int flog(int v); int main() { int n,k; cin>>n; DWORD startTime=GetTickCount(); k=flog(n); DWORD endTime=GetTickCount(); cout<<k<<" "<<endTime-startTime; } int flog(int v) { if(v==1) return 0; else if(v==2) return 1; else return flog(v-1)+flog(v-2); }
明显发现优化后效率更高.
原文：https://www.cnblogs.com/-Iris-/p/12245690.html