文档介绍：该【分治与递归策略课件 】是由【zhangkuan1438】上传分享，文档一共【83】页，该文档可以免费在线阅读，需要了解更多关于【分治与递归策略课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
第2讲分分治与递递归策略略
2
算法总体体思想
将一个难难以直接接解决的的规模较较大的问问题分解解为若干干个规模模较小的的子问题题,并各个击破破,分而而治之。
n/16
n
n/4
n/4
n/4
n/4
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
n/16
3
将求出的的较小规规模的问问题解合合并成一一个较大大规模的的问题解解,并自底向上地求出原问题题的解。
最顶层问题
a为分解的子问问题数量;
n/b为每个子问题题的数据规模模;
f(n)为合并子问题题解所消耗的的时间。
4
分治算法的基基本思想是将将一个规模为为n的问题分分解为a个规规模较小的子子问题,这些些子问题互相相独立且与原原问题相同。。递归地解这这些子问题,,然后将各个个子问题的解解合并得到原原问题的解。
5
分治算法所能能解决问题一一般具有以下下几个特征::
缩小问题规模模可以降低解解决问题的难难度;
可以将子问题题的解合并为为原问题解;;
问题分解出的的各个子问题题是相互独立立的,即子问问题之间不包包含公共的子子问题。
6
分治算法的算算法框架
divide-and-conquer(P){
if(|P|<=n0)adhoc(P);//解决规模模小的问题
//将问题P分解为子问题P1,P2,...,Pa;
for(i=1,i<=a,i++)
yi=divide-and-conquer(Pi);//递归的求解各子问题
returnmerge(y1,...,ya);//合并为原问题的解解
}
7
一个分治算法法将规模为n的问题分成成a个规模为为n/b的子子问题。设分分解阈值n0=1,且adhoc解规规模为1的问问题耗费1个个单位时间。。再设将原问问题分解为a个子问题以以及用merge将a个个子问题的解解合并为原问问题的解需用用f(n)个个单位时间。。用T(n)表示该分治治算法解规模模为|P|=n的问题所所需的计算时时间,则有下下列递归方程程:
通过求解递归归方程得到递递归算法的时时间复杂性。。
分治算法的复复杂性分析
8
替换方法
递归树方法
公式法
求解递归方程程的三种方法法:
9
替换方法
替换方法的主主要思想是首首先推测出递递归方程的解解,然后后代入递归方方程,查看是是否满足条件件。
适用比较容易易猜出递归解解的情形。
①猜测出递递归解的形式式
②用数学归归纳法找出使使解真正有效效的常数
替换方法解递递归方程的基基本步骤:
10
例:T(n)=2T(n/2)+n(2路归归并)
假设解对n/2成立,即即T(n/2)≤c(n/2)lg(n/2)
将其对递归方方程进行替换换,得:
T(n)=2T(n/2)+n
≤2(c(n/2)lg(n/2))+n
≤cnlg(n/2)+n
≤cnlgn-cnlg2+n
=cnlgn-cn+n
当c≥1时,,显然cnlgn-cn+n≤cnlgn
根据O符号定定义,证明猜猜测正确。
数学归纳法::
猜测出解为T(n)=O(nlgn)
证明存在某个个常数c,使使得T(n)≤cnlgn