递推,递归与分治
递推
- 什么是递推
递推,就是从小的解开始,一步一步推到最优解的过程。
- 如何递推
这就要看具体情况,想出递推式,然后一步一步递推即可。
- 递推如何应用
讲这个之前,我们不妨先讲一讲递推如何具体实现。
第一步是先初始化。切记!
有两种表示方法:
-
数组递推法,如 f[i] = f[i-1]+f[i-2];
-
记忆化搜索,若冗余状态比较多则需要记忆化,否则直接调用即可。注意递归的结束,否则MLE或TLE后果自负。
那么,什么是冗余状态呢?
这是一个关于f(5)的解答树,可以看见,红色的都是被重复计算的,很多节点被重复计算了多次,若数比较大,重复计算的可不止这几个,而是一颗巨大的子树。
那么,没有记忆化的f究竟有多慢呢?
我们可以做一个测试。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
int f(int i)
{
if(i == 0)return 0;
if(i == 1)return 1;
return f(i-1)+f(i-2) % 233333333;
}
int main(int argc,char** argv)
{
int i = atoi(argv[1]);
cout<<f(i)<<endl;
cout<<"时间:"<<clock()/double(CLOCKS_PER_SEC);
}
左图是笔者的vim截图,右图时代码在笔者机器上面的运行结果。
可以看出,速度的增长是指数级的。
我们在计算时用数组记录已经算出的结果,就是记忆化搜索的核心思想。
但是,如果冗余状态比较少,或者没有,我们也可以不用记忆化。就像我们计算阶乘时,,很容易可以看出,每个状态只由前一个推出,所以,每个状态只被计算了一次。
递归
这个其实不用多说递归就是递推和回归,记忆化搜索就是递归的过程。
我们来看一个类似递归的故事:
-
皇帝要计算f(5)(就是5!).
-
皇帝问大臣:f(4)=?
-
大臣问师公:f(3)=?
-
师公问先生:f(2)=?
-
先生问小学生:f(1)=?
-
小学生口算:f(1)=1
-
先生口算:f(2)=2
-
师公口算:f(3)=6
-
大臣口算:f(4)=24
-
皇帝口算:f(5)=120
皇帝满意了。
虽然这个比喻不是特别恰当,但是也能说明一些事情。
根据C++语言的特性,调用自己和调用其他函数并没有任何区别,都是压栈并修改当前代码行。
原文链接: https://www.cnblogs.com/inkuniverse/p/jc2.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/363930
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!