资源描述：
《第2章递归与分治ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析>递归与分治2.2分治算法的基本思想Divide-and-Conquer(P)if(
2、P
3、<=n0)Adhoc(P);直接求解问题pdividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);将p1,p2,…pk的解y1,y2,…yk合并成p的解问题的规模阀值算法一般模式将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互
4、独立可分别求解,再将k个子问题的解合并成原问题的解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止.在分治法中,子问题的解法通常与原问题相同,自然导致递归过程.应用当中,通常将问题分解为k个(k=2)大小相等的子问题.1算法设计与分析>递归与分治设问题P(n)分解成k个规模为n/m的子问题,阈值n0=1,求解P(1)的时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则分治法解规模为n的问题的最坏时间复杂性函数T(n)满足:T(n)=算法的时间复杂性T(1)=O(1
5、)T(n)=kT(n/m)+f(n)解得:适用问题大数相乘,矩阵乘法,快速富立叶变换,棋盘覆盖,排序,选择等.2算法设计与分析>递归与分治2.3递归方程1代入法解递归方程设a,b,c是非负整数：bn=1T(n)≤aT(n/c)+bnn＞1其中，a是子问题的个数，c是递减的步长设n=ck，k是正数3算法设计与分析>递归与分治…4算法设计与分析>递归与分治5算法设计与分析>递归与分治讨论：当ac时即6算法设计与分析>递
6、归与分治2生成函数法解递归方程用生成函数法解常系数线性递归方程如递归函数n=0n=1n>17算法设计与分析>递归与分治设生成函数为：8算法设计与分析>递归与分治令：9算法设计与分析>递归与分治例有数列0，1，5，19，65，211…写出线性递归关系，并求出非递归解。解：递归关系n=0n=1n>1生成函数10算法设计与分析>递归与分治11算法设计与分析>递归与分治与上面G(x)对比3.常系数线性递归方程定义：递推关系R其中a1,a2,…,ak是常数，n=k,k+1…此递推关系为常系数线性递推关系定义：
7、方程称为常系数线性递推关系R的特征方程，它的根q1,q2,…qk叫常系数线性递推关系R的特征根12算法设计与分析>递归与分治qi,可以是复数定理：设q是一个非0的实数或复数（1）则H(n)=qn是递推关系R的一个解，当且仅当q是它的一个特征根。（2）如能找到两个不同的根q1,q2,则是H(n)的解。（3）若q1,q2,q3…qt是递推关系的不等特征根，且c1,c2,…ct是常数，则是H(n)的解。（4）若q1,q2,q3…qt是递推关系的不等特征根，qi是特征方程的e重根，且c1,c2,…ct，ci
8、1,ci2,…cie13算法设计与分析>递归与分治是常数，则是H(n)的解。例：用递推关系表示Fibonacci数列的通项解：特征方程q2–q-1=014算法设计与分析>递归与分治通解：根据初始条件：F(0)=0F(1)=1解得：15算法设计与分析>递归与分治例：求常系数线性递归方程的通解解：特征方程重根通解初始条件H(0)=1,H(1)=3解得16算法设计与分析>递归与分治通解上面讨论是齐次常系数线性递归方程，如果是非齐次常系数线性递归方程如何求解?例如：其中a1,a2,…,ak是常数，n>k则令
9、分别是是非齐次常系数线性递归方程齐次解及其特解其通解为：17算法设计与分析>递归与分治若且1不是齐次方程的根，则特解为若1是齐次方程的m重根，则特解为：若f(n)=an的形式，且即a不是齐次方程的特征根,则:若a是齐次方程的m重特征根,则:18算法设计与分析>递归与分治例：汉诺塔算法分析移动次数：n=0n=1n>1解：齐次方程H(n)-2H(n-1)=0特征方程q-2=0特征根q=2通解特解：f(n)=1=n019算法设计与分析>递归与分治代入：p-2p=1,p=-1通解：H(0)=0C=1即20算
10、法设计与分析>递归与分治例分治算法中的递归方程一般的，递归的时间复杂性可归结为递归方程：1n=1T(n)≤aT(n/b)+D(n)n＞1其中，a是子问题的个数，b是递减的步长，D(n)是合成子问题的开销。21算法设计与分析>递归与分治T(n)=aT(n/b)+D(n)=a(aT(n/b2)+D(n/b))+D(n)=k–1i=0=akT(1)+aiD(n/bi)=ak+aiD(n/bi)k–1i=0这里bk=n，所以k=logbn。于是：由此可知，T(n)的首
