第三章分治与平衡.ppt

《第三章分治与平衡.ppt》由会员分享，可在线阅读，更多相关《第三章分治与平衡.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Just_2011computer2 2第三章第三章 分治与平衡分治与平衡要想直接解决一个较大的问题，有时是相当困难。分而治之（divide-and-conquer）的设计思想是，把一个难以下手的大问题，分割成一些较小的子问题，以便各个击破。因为这些子问题较小，可能比原问题容易处理一些。如果能把一个输入量为n的问题分割成k个子问题，1kn，且这些子问题都有可解，并且能利用这些子问题的解求出原问题的解，那么这种分治方法便是可行的。由分治法产生的子问题往往是原问题较小模式，为使用递归技术提供了方便。反复应用分治手段，可以使子问题与原问题类型一致而体积却越来越小，最终使子问题缩小到母须再分且容易求解

2、。3 3第三章第三章 分治与平衡分治与平衡分治法步骤：1、分解：将原问题分解为若干规模较小，相互独立，与原问题形式上相同的子问题。2、解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。3、合并：将各个子问题的解合并为原问题的解。4 45 5需要进一步研究的问题：根据分治法的分割原则，应把原题分为多少个子问题才较适宜？每个子问题是否大小一样及怎样才为适当？目前很难给出科学的回答，实践表明k常取2，子问题大小相等，比较有效。子问题大小相等的做法出自一种平衡（balancing）子问题的思想。平衡思想普遍存在，比如木桶定理：一只沿口不齐的木桶，最短的那块木板或低缺口决定它的盛水容量

3、。为提高木桶的整体效益，则要求补齐最短木板的长度以及使各木板长度相等。木桶理论是由美国管理学家彼得提出的。组成木桶的木板如果长短不齐，那么木桶的盛水量不是取决于最长的那一块木板，而是取决于最短的那一块木板。这就是说构成组织的各个部分往往是优劣不齐的，而劣势部分往往决定整个组织的水平。7 7第一节第一节 合并排序合并排序考虑n个元素的排序问题，就是将这些元素排列成一个有序序列，我们这里假定没有相等的元素，排成递增序列。一、选择整序（Selection Sort）将这几个元素存于一个数组之中，首先通过n-1次比较找出这个数组中的最小元素，并将这个元素与第一个数组元素交换（如果正好第一个数组元素是最

4、小元素，则不必交换）。第i次在剩余的n-i+1个元素（数组中第i个到第n个元素）中找出最小元素与第i个元素交换，重复以上做法，直到i=n-1为止。这个算法中，找第个最小元素，需要n-i次比较，所以总的比较次数：T(n)=(n-1)+(n-2)+2=1=1/2n(n-1)也可以用递归关系：1010二、冒泡整序这种排序的基础思想是，在整个过程中，每次仅进行相邻两元素比较。不像选择整序那样一个较小的元素一下子放在顶部，而是每次向上移动一步，缓缓上升到顶部，象一个气泡从水底向上运动一样。比如序列：8，3，4，9，7第1次比较：3，8，4，9，7 第1个与第2个数比较第2次比较：3，4，8，9，7 第2

5、个与第3个数比较第3次比较：3，4，8，9，7 第3个与第4个数比较第4次比较：3，4，8，7，9 第4个与第5个数比较，最后位是最大值第5次比较：3，4，8，7，9 第1个与第2个数比较第6次比较：3，4，8，7，9 第2个与第3个数比较第7次比较：3，4，7，8，9 第3个与第4个数比较，第4位是次大值第8次比较：3，4，7，8，9 第1个与第2个数比较第9次比较：3，4，7，8，9 第2个与第3个数比较，停止，因为没有交换的操作，终止算法。最坏情况与平均特性至少是O(n2)阶。11111.1 引言引言三、合并排序 选择整序可以看成分成大小不等的两个子问题（n-1个与1个）的分治法的递归应

6、用。合并排序是原问题分成大小相等的两个子问题，先把两个子集的元素排成非递减序，然后把这两个排序好的子序列合并成一个非递减序列。12121313合并排序主程序伪代码：MergeSort(low,high)/Alow:high是一个全程数组，含有high-low+1个待排序的元素 integer low,high;if low mid then for k from j to high do Bi=Ak;i=i+1;endfor else for k from h to mid do Bi=Ak;i=i+1;endfor endif for k from low to high do Ak=Bk;

7、endforend Merge15151616第二节第二节 二分搜索技术二分搜索技术 二分搜索技术是运用分治策略的典型例子。问题：给定已排好序的n个元素a0:n-1，现要在这个元素中找出一特定元素x。首先较易想到的是用顺序搜索方法，逐个比较a0:n-1中元素，直至找出元素x，最坏情况需要作个比较，即需要O(n)。这个方法设有很好利用n个元素已排好序这个条件。17171818二分搜索算法伪代码：BinarySearch(A,n,x)/A1:n是一个非降序列的元素数组，判断x是否在A中出现/若出现，返回位置j，否则返回j0 integer left,right，mid，j；left=1;right

8、=n;while leftright do mid=(left+right)/2;if x=Amid then j=mid;return;elseif xAmid then left=mid+1;else right=mid 1;endif endwhile j=0/未找到end BinarySearchwhile 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行O(log2n)次。由于每次循环需耗时O(1)，因此在最坏情况下，总的时间复杂性为O(log2n)。1919第三节第三节 整数乘法和矩阵乘法整数乘法和矩阵乘法一、整数乘法20202222232

9、3二、Strassen矩阵乘法24242525棋盘覆盖在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。棋盘覆盖当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种

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

11、+s)/特殊方格在此棋盘中 chessBoard(tr,tc+s,dr,dc,s);else/此棋盘中无特殊方格 /用 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)/特殊方格在此棋盘中 chessBoard(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

12、(n)=O(4k)渐进意义下的最优算法2929第四节 顺序统计 顺序统计（order statistics）问题是要求从n个元素中选出第k个最小元素。如果n个元素已经排成了非递减序，找出第k个最小元素就十分容易。首先排序这n个元素就要耗费的时间O(nlog2n)。这里的问题只需要对某个固定的找出第k个最小元素，并不需要将n个元素排序，需要的时间应当比排序的时间少。采用分治策略的方法可以在O(n)的时间内找到第个最小元素。3030第五节 顺序统计的期望时间 无论是最坏情况下还是期望意义下，要从个元素中选出第k个最小元素，至少需要进行n-1次比较。下面的算法对期望复杂性（平均复杂性）是比较好的。第

13、六节第六节 循环赛日程表循环赛日程表 分治法不仅可以用来设计算法,而且在其他方面也有广泛应用。例如可以用分治思想来设计电路、构造数学证明等。现举一例加以说明。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n-1天。按此要求可将比赛日程表设计成有n行和n-l列的一个表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。按分治策略，我们可以将所有选手对分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分

14、割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。下图所列出的正方形表是4个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手2和选手3至选手4第1天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手2和选手3至选手4在后2天的比赛日程。这种安排是符合要求的。循环赛日程表1234567821436587341278564321876556781234658721437856341287654321快速排序在快速排序中，记录的比较和交换是从两端

15、向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。templatevoid QuickSort(Type a,int p,int r)if(pr)int q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序 快速排序templateint Partition(Type a,int p,int r)int i=p,j=r+1;Type x=ap;/将 x的元素交换到右边区域 while(true)while(a

16、+i x);if(i=j)break;Swap(ai,aj);ap=aj;aj=x;return j;初始序列6,7,5,2,5,8j-;5,7,5,2,6,8i+;5,6,5,2,7,8j-;5,2,5,6,7,8i+;完成6,7,5,2,5,85,2,5 6 7,8a0a1a2a3a4a5a6a7a8a945326754343221256798ijtemp45快速排序快速排序:对于给定的数组内的数据对于给定的数组内的数据,如何排序如何排序?在排序之前在排序之前,先设定一个哨兵先设定一个哨兵值值,一般选择一般选择a0,将其值赋给一个将其值赋给一个临时变量临时变量:temp=a0;a0a1a2

17、a3a4a5a6a7a8a945326754343221256798ijtemp45快速排序快速排序:与合并排序类似，合并排序为平分数据与合并排序类似，合并排序为平分数据序列，而快速排序通过序列，而快速排序通过确定第一个元素在数组中确定第一个元素在数组中的位置的位置将序列分为左右两部分。将序列分为左右两部分。然后开始左右移动下标然后开始左右移动下标i、j值，值，直到（直到（ai=temp且且aj=temp且且aj=temp且且aj=temp，aj=temp且且aj=temp且且aj=temp且且aj=temp，aj=temp且且aj=temp且且aj=temp，aj=temp且且aj=temp

18、且且aj=temp，aj=temp且且aj=temp，aj=temp且且aj=temp且且aj=temp）或（）或（i=j）停止）停止.a0a1a2a3a4a5a6a7a8a925322132344554676798ijtemp45快速排序快速排序:与合并排序类似，合并排序为平分数据与合并排序类似，合并排序为平分数据序列，而快速排序通过序列，而快速排序通过确定第一个元素在数组中确定第一个元素在数组中的位置的位置将序列分为左右两部分。将序列分为左右两部分。这时这时45的位置在数组中就已经的位置在数组中就已经确定了，接下来我们只需要对确定了，接下来我们只需要对04数组元素以及数组元素以及69数组元

19、素两部分数组元素两部分进行排序即可，原理同上。进行排序即可，原理同上。templateint RandomizedPartition(Type a,int p,int r)int i=Random(p,r);Swap(ai,ap);return Partition(a,p,r);快速排序 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)