网上做问卷报酬不错的网站是,iis 如何新建网站,自己制作网站做外贸赚钱吗,用vs做网站界面1.普通递归
这里观察f[4]的递归树代替f[10]的递归树#xff08;后者比较大#xff0c;画不下#xff09;。 使用递归求解的时候复杂度为T(n)T(n−1)T(n−2)T(n)T(n-1)T(n-2)T(n)T(n−1)T(n−2)#xff0c;观察递归树#xff0c;发现降速最快的是最右边每次减2#xff0c…1.普通递归
这里观察f[4]的递归树代替f[10]的递归树后者比较大画不下。 使用递归求解的时候复杂度为T(n)T(n−1)T(n−2)T(n)T(n-1)T(n-2)T(n)T(n−1)T(n−2)观察递归树发现降速最快的是最右边每次减2因此n2\frac{n}{2}2n层以上的部分肯定是满二叉树因此时间复杂度肯定是Ω(2n2)\Omega(2^{\frac{n}{2}})Ω(22n)的再加上其他节点因此我们可以大概认为时间复杂度为O(2n)O(2^n)O(2n)空间复杂度为树的深度为O(n)O(n)O(n)
实现代码
ll Fibo(ll n)
{if(n2) return n;return Fibo(n-1)Fibo(n-2);
}2.尾递归
通过改变函数的形式能够让结果在最底层调用时直接返回。这样我们就可以在每一层函数尾调用自身来实现尾递归。因为编译器发现函数最后是尾调用直接返回另一个函数的时候将不会保存原函数的栈帧因为已经执行结束而是直接带着上一个栈帧的结果直接在原地进入下一栈帧。这样就没有递归调用时空间的额外消耗。
对于本问题使用尾递归的话时间复杂度为O(n)O(n)O(n)空间复杂度为O(1)O(1)O(1)
ll Fibo2(ll n,ll x,ll y)//y保存当前项调用时x0y1表示当前项为1
{if(1 n) return y;return Fibo2(n-1, y, xy);
}
3. 记忆化搜索
为了避免对已经计算过的值再次计算我们用一个数组保存已经计算过的值。这样的时间复杂度将变为O(n)O(n)O(n)空间复杂度也为O(n)O(n)O(n)
ll Work3(ll n, ll* ans)
{if(n2) return ans[n]n;if(ans[n]) return ans[n];return ans[n]Work3(n-1, ans)Work3(n-2, ans);
}ll Fibo3(ll n)
{ll *ans new ll[n5]();ll ret Work3(n, ans);delete[] ans;return ret;
}4. 递推
斐波那契有递推公式Fibo[n]Fibo[n−1]Fibo[n−2]Fibo[n]Fibo[n-1]Fibo[n-2]Fibo[n]Fibo[n−1]Fibo[n−2]因此可以用递推解决。如果记忆所有项的话空间复杂度为O(n)O(n)O(n)如果不记忆的话空间复杂度为O(1)O(1)O(1)。时间复杂度为O(n)O(n)O(n)
ll Fibo4(ll n)
{ll *ans new ll[n5];ans[1]1;for(ll i2;in;i) ans[i]ans[i-1]ans[i-2];ll retans[n];delete[] ans;return ret;
}性能测试
#include iostream
#include algorithm
#include ctimeusing namespace std;typedef long long ll;
typedef ll (*FP)(ll);ll Fibo1(ll n)
{if(n2) return n;return Fibo1(n-1)Fibo1(n-2);
}ll Work2(ll n,ll x0,ll y1)//y保存当前项调用时x0y1表示当前项为1
{if(1 n) return y;return Work2(n-1, y, xy);
}ll Fibo2(ll n)
{return Work2(n);
}ll Work3(ll n, ll* ans)
{if(n2) return ans[n]n;if(ans[n]) return ans[n];return ans[n]Work3(n-1, ans)Work3(n-2, ans);
}ll Fibo3(ll n)
{ll *ans new ll[n5]();ll ret Work3(n, ans);delete[] ans;return ret;
}ll Fibo4(ll n)
{ll *ans new ll[n5];ans[1]1;for(ll i2;in;i) ans[i]ans[i-1]ans[i-2];ll retans[n];delete[] ans;return ret;
}void Test(ll n,FP fp[])
{clock_t S,E;for(int i0;i4;i){int T10;double sum0;for(int j0;jT;j){Sclock();fp[i](n);Eclock();sum(double)(E-S)/CLOCKS_PER_SEC;}cout方法i1平均用时sum/Tsendl;}
}int main()
{FP fp[4]{Fibo1,Fibo2,Fibo3,Fibo4};ll n;cout请输入需要查询斐波那契数列第几项; cinn;Test(n,fp);return 0;
}运行结果 性能分析
可以看到后面几种方法的复杂度相差不多但是同样是递归处理尾递归比普通递归的复杂度明显优秀很多所以如果可以的话应该尽量将递归变成尾递归的方式进行处理。
