算法设计与分析递归与分治学习教案

1、会计学1算法设计与分析算法设计与分析(fnx) 递归与分治递归与分治第一页，共39页。第2页/共39页第二页，共39页。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= l对这k个子问题分别求解。如果子问题的规模仍然不够(bgu)小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。第3页/共39页第三页，共39页。l对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此(rc)递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4

2、)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治分治(fn zh)法的基本思想法的基本思想第4页/共39页第四页，共39页。l将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步(zhb)求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治法的基本分治法的基本(jbn)思想思想第5

3、页/共39页第五页，共39页。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治法的基本分治法的基本(jbn)思想思想l将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步(zhb)求出原来问题的解。第6页/共39页第六页，共39页。分治法的设计思想是，将一个难以直接解决的大分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各问题，分割成一些规模较小的相同问题，

4、以便各个击破个击破(g g j p)，分而治之。，分而治之。2.1 分治分治(fn zh)法的基本思想法的基本思想第7页/共39页第七页，共39页。2.1 分治法的基本分治法的基本(jbn)思想思想第8页/共39页第八页，共39页。第9页/共39页第九页，共39页。大量实践证明：在用分治法设计算法时，将一个问题分成(fn chn)大小相等的k个子问题的处理方法是行之有效的第10页/共39页第十页，共39页。复杂性分析：设一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解(fnji)阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解(fnji)为k个子问题

5、以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。则有：11)()/() 1 ()(nnnfmnkTOnT通过(tnggu)迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT第11页/共39页第十一页，共39页。第12页/共39页第十二页，共39页。00)!1(1!nnnnn边界条件边界条件递归方程递归方程(fngchng)第13页/共39页第十三页，共39页。110)2() 1(11)(nnnnFnFnF第14页/共39页第十四页，共39页。110)2() 1(11)(nnnnFnFnF第15页/共39页第十五页，共39页。设R=r1,r2,rn

6、是要进行排列的n个元素(yun s)，Ri=R-ri。集合X中元素(yun s)的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中(qzhng)r是集合R中唯一的元素；当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 第16页/共39页第十六页，共39页。第17页/共39页第十七页，共39页。l例例3 二分搜索技术二分搜索技术l给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要，现要在这

7、在这n个元素中找出一特定个元素中找出一特定(tdng)元素元素x。l分析：分析：第18页/共39页第十八页，共39页。二分二分(r fn)(r fn)搜索算法：搜索算法：int binarySearch(int a, int x, int n) int binarySearch(int a, int x, int n) left = 0; right = n - 1; left = 0; right = n - 1; while (left = right) while (left amiddle) left = middle + 1; if (x amiddle) left = middle

8、 + 1; else right = middle - 1; else right = middle - 1; return -1; / return -1; / 未找到未找到x x l例例3 二分二分(r fn)搜索技术搜索技术2.4 分治法的应用分治法的应用第19页/共39页第十九页，共39页。A和B的乘积矩阵C中的元素Ci,j定义为: nkjkBkiAjiC1u传统(chuntng)方法：O(n3)l例例4 Strassen矩阵矩阵(j zhn)乘法乘法第20页/共39页第二十页，共39页。使用与上例类似的技术(jsh)，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方

9、程C=AB重写为：u分治(fn zh)法:222112112221121122211211BBBBAAAACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3) 没有改进没有改进22)()2/(8) 1 ()(2nnnOnTOnT第21页/共39页第二十一页，共39页。u改进(gijn):为了降低时间复杂度，必须减少(jinsho)乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM112

10、2213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC复杂度分析复杂度分析T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进22)()2/(7) 1 ()(2nnnOnTOnT第22页/共39页第二十二页，共39页。在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同(b tn)，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同(b tn)形态的L型骨牌覆盖给定的特殊棋盘上除

11、特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。2.4 分治分治(fn zh)法的应用法的应用第23页/共39页第二十三页，共39页。当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格(fn )必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格(fn )。为了将这3个无特殊方格(fn )的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。 第24页/共39页第二十四页，共39页。void chessBoard(int tr, int

12、 tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘(qpn) / 覆盖左上角子棋盘(qpn) if (dr tr + s & dc tc + s) / 特殊方格在此棋盘(qpn)中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘(qpn)中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1,

13、 tc+s-1, s); / 覆盖右上角子棋盘(qpn) if (dr = tc + s) / 特殊方格在此棋盘(qpn)中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘(qpn)中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊(tsh)方格在此棋盘中 chessBoar

14、d(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 复杂度分析复杂度分析T(n)=O(4k) 渐进意义下的最优算法00) 1 () 1(4) 1 ()(kkOkTOkT第25页/共39页第二十五页，共39页。void mergeSort(int a, int left, int right) if (leftright) /至少有2个元素(yun s) int i=(left+right)/2; /取中点 me

15、rgeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到数组b copy(a, b, left, right); /复制回数组a 复杂度分析复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法11)()2/(2) 1 ()(nnnOnTOnT第26页/共39页第二十六页，共39页。算法(sun f)mergeSort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13

16、27 38 49 65 76 97第27页/共39页第二十七页，共39页。lvoid MergePass(int x, inty,int s, int n)li=0;lwhile(i=n-2*s)l Merge(x,y,i,i+s-1,i+2*s-1);l i=i+2*s;ll if(i+sn)l Merge(x,y,i,i+s-1,n-1);l elsel for(j=i;j=n-1;j+)l yj=xj;l第28页/共39页第二十八页，共39页。第29页/共39页第二十九页，共39页。&最坏时间最坏时间(shjin)复杂度：复杂度：O(nlogn)&平均时间平均时间(shj

17、in)复杂度：复杂度：O(nlogn)&辅助空间：辅助空间：O(n)&稳定性：稳定稳定性：稳定2.4 分治分治(fn zh)法的应用法的应用第30页/共39页第三十页，共39页。给定线性序集中(jzhng)n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素例例7 元素元素(yun s)选择问题选择问题第31页/共39页第三十一页，共39页。int partition (int a, int p, int r) pivot=ap; low = p; high = r; while (lowhigh) while (low=pivot) -high; alow=ahig

18、h; while (lowhigh&alow =pivot); +low; ahigh=alow; alow = pivot; return low; 第32页/共39页第三十二页，共39页。随机(su j)划分：int randomizedPartition (int a,int p, int r) i = random(p,r); swap(ai, ap); return partition (a,p, r); 第33页/共39页第三十三页，共39页。给定(i dn)线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素randomizedSelect(int a,int p,int r,int k) /在在ap.r中找第中找第k小的元素小的元素(yun s) if (p=r) return ap; i=randomizedpartition(p,r), j=i-p+1; if (k=j) return randomizedSelect(a,p,i,k); else return randomizedSelect(a,i+1,r,k-j); 调用调