Divide and conquer method

  1. 云栖社区>
  2. 博客列表>
  3. 正文

Divide and conquer method

graylee 2013-11-08 19:18:00 浏览126 评论0

摘要:   分治法是最广泛使用的算法设计方法之一,其基本思想:把大问题分解成一些较小的问题,然后由小问题的解方便地构造出大问题的解。   分治法说穿了就是把问题放小,如果被分的问题还是比较大,那么久继续分下去。

  分治法是最广泛使用的算法设计方法之一,其基本思想:把大问题分解成一些较小的问题,然后由小问题的解方便地构造出大问题的解。

  分治法说穿了就是把问题放小,如果被分的问题还是比较大,那么久继续分下去。为了能清晰地反映采用分治策略设计算法的基本步骤,下面用一个称之为抽象化控制的过程来非形式的描述算法的控制流向,下面笔者举例来说明这个问题。

void div(p,q) {
int n,A[n]; //定义成全程变量
int m,p,q; //1≤p≤q≤n
if(small(p,q)) return(answer(p,q));
else
{
m = divide(p,q); //p≤m<q
return (combine(div(p,m),div(m+1,q)));
};
}//div

 

  在这个算法中,small(p,q)是一个布尔值函数,它用以判断输入为A(p:q)的问题是否小到无需进一步细分就能算出其答案的程度。若是,则调用能直接计算此规模下的子问题解的函数answer(p,q);若否,则调用分割函数divide(p,q),返回一个新的分割点m(整数)。于是,原问题被分成输入为A(p:m)和A(m+1:q)的两个子问题。对这两个子问题分别递归调用div得到各自的解x和y,再用一个合并函数combine(x,y)将这两个子问题的解合成原问题(输入为 A(p,q))的解。倘若所分成的两个子问题的输入规模大致相等,则div总的计算时间可用下面的递归关系式来表示:
            g(n) 当n足够小,                                                                    

T(n)=                                             

    2T(n/2)+f(n) 否则
其中,T(n)是输入规模为n的div的运行时间,g(n)是输入规模足够小以至于能直接求解时的运行时间,f(n)是combine的时间

显然用递归过程描述以分治法为基础的算法是理所当然的,但为了提高效率,往往需要将这一递归形式转换成迭代形式。例如下面这个算法:

void div1(p,q) {
//div的迭代模型,定义了一个适当大小的工作栈
int s,t;
intiStack(sqStack); //定义工作栈sqStack
L1:while(!small(p,q)) {
m = divied(p,q); //确定如何分割输入
push(sqStack,(p,q,m,0,2)); //处理第一次递归调用
q = m;
};//while
t = answer(p,q);
while(!StackEmpty( sqStack )) {
pop(sqStack,(p, q, m, s, ret)); //退栈,ret为返回地址
if(ret==2) {
push(sqStack,(p, q, m, t, 3)); //处理第二次递归调用
p = m + 1;
go to L1;}
else {
t = combine(s,t); //将两个子问题的解合并成一个解
};//if
};//while
return t;
}//div1   当然,这个算法还可以简化

 

【云栖快讯】你想见的Java技术专家都在这了,向大佬提问,有问题必答  详情请点击

网友评论

graylee
文章220篇 | 关注13
关注
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
云数据库PPAS版,是阿里云与EnterpriseDB公司合作基于PostgreSQL高度兼... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航