第5章减治法(完).ppt

《第5章减治法(完).ppt》由会员分享，可在线阅读，更多相关《第5章减治法(完).ppt（73页珍藏版）》请在三一文库上搜索。

1、第5章 减治法,2019/3/11,第5章 减治法,Page 2,第5章 减治法,5.1 减治法的设计思想,5.2 查找问题中的减治法,5.3 排序问题中的减治法,5.4 组合问题中的减治法,2019/3/11,第5章 减治法,Page 3,规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系： （1）原问题的解只存在于其中一个较小规模的子问题中； （2）原问题的解与其中一个较小规模的解之间存在某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。,5.1 减治法的设计思想,2019/3/11,第5章

2、 减治法,Page 4,5.1 减治法的设计思想,2019/3/11,第5章 减治法,Page 5,例：计算an的值，应用减治技术得到如下计算方法：,应用分治法得到an的计算方法是：,O (log2n),O (nlog2n),5.1 减治法的设计思想,2019/3/11,第5章 减治法,Page 6,所以，通常来说，应用减治法处理问题的效率是很高的，一般是O(log2n)数量级。,减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：,5.1 减治法的设计思想,对比分治法：,2019/3/11,第5章 减治法,Page 7,5.1 减治法的设计

3、思想,一个简单的例子两个序列的中位数,问题描述：一个长度为n（n1）的升序序列S，处在第n/2个位置的数称为序列S的中位数 。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。,A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，则中位数为13,2019/3/11,第5章 减治法,Page 8,5.1 减治法的设计思想,想法：分别求出两个序列的中位数，记为a和b；比较a和b，有下列三种情况： a = b：则a即为两个序列的中位数； a b：则中位数只能出现在b和a之间

4、，在序列A中舍弃a之后的元素得到序列A1，在序列B中舍弃b之前的元素得到序列B1； 在A1和B1中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。,2019/3/11,第5章 减治法,Page 9,5.1 减治法的设计思想,对于两个给定的序列A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列A和B的中位数的过程。,2019/3/11,第5章 减治法,Page 10,5.1 减治法的设计思想,1. 循环直到序列A和序列B均只有一个元素 1.1 a = 序列A的中位数； 1.2 b = 序列B的中位数； 1.3 比较a和b，执行下面

5、三种情况之一： 1.3.1 若a=b，则返回a，算法结束； 1.3.2 若ab，则在序列A中舍弃a之后的元素，在序列B中舍弃b之前的元素，转步骤1； 2. 序列A和序列B均只有一个元素，返回较小者；,2019/3/11,第5章 减治法,Page 11,5.2.1 折半查找,5.2.2 二叉查找树 5.2.3 选择问题,5.2 查找问题中的减治法,2019/3/11,第5章 减治法,Page 12,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区

6、继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,5.2.1 折半查找,2019/3/11,第5章 减治法,Page 13,例：查找值为14的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3114,1814,714,14=14,查找成功！,2019/3/11,第5章 减治法,Page 14,2019/3/11,第5章 减治法,Page 15,判定树描述折半查找的判定过程。 长度为n的判定树的构造方法为： （1）当n=0时，判定树为空； （2）当n0时，判定树的根

7、结点是有序表中序号为mid=(n+1)/2（取地板）的记录，根结点的左子树是与有序表r1 rmid-1相对应的判定树，根结点的右子树是与rmid+1 rn相对应的判定树。,2019/3/11,第5章 减治法,Page 16,具有11个结点的判定树,在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有n个结点的判定树的深度为 ，所以，查找成功时进行的比较次数最多为,2019/3/11,第5章 减治法,Page 17,以深度为k的满二叉树（n=2k-1）为例，假设表中每个记录的查找概率相等，即pi=1/n，而树的第i层上有2i-1个结

8、点，则折半查找的平均查找长度为：,所以，折半查找的时间复杂度为：O(log2n),2019/3/11,第5章 减治法,Page 18,二叉查找树，又称二叉排序树，是具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值； （3）它的左右子树也都是二叉排序树。,5.2.2 二叉查找树,2019/3/11,第5章 减治法,Page 19,2019/3/11,第5章 减治法,Page 20,由二叉排序树的定义，在二叉排序树root中查找给定值k的过程是： 若root是空树，则查找失败； 若k根结点的值，

9、则查找成功； 否则，若k根结点的值，则在root的左子树上查找； 否则，在root的右子树上查找； 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。 二叉排序树的查找效率就在于只需要查找两个子树之一。,5.2.2 二叉查找树,2019/3/11,第5章 减治法,Page 21,二叉排序树的结点结构为： struct BiNode int data; /结点的值，假设查找集合的元素为整型 BiNode *lchild, *rchild; /指向左、右子树的指针 ;,2019/3/11,第5章 减治法,Page 22,在二叉排序树上查找关键码等于给定值的结点的过程

10、，恰好走了一条从根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数最少为1次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。具有n个结点的二叉树的深度至少是 ，至多是n，所以，二叉排序树的查找性能在O(log2n)和O(n)之间。,2019/3/11,第5章 减治法,Page 23,设无序序列 T =(r1, r2, , rn)，T 的第k（1kn）小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找 T 的第k小元素的问题称为选择问题。特别地，将寻找第n/2小元素的问题称为中值问题。,5.2.3 选择问题,2019

11、/3/11,第5章 减治法,Page 24,（1）若k=s，则rs就是第k小元素； （2）若ks，则第k小元素一定在序列rs+1 rj中；,考虑快速排序中的划分过程，一般情况下，设待划分的序列为ri rj，选定一个轴值将序列ri rj进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则：,2019/3/11,第5章 减治法,Page 25,选择问题的例子:,2019/3/11,第5章 减治法,Page 26,2019/3/11,第5章 减治法,Page 27,最好情况：每次划分的轴值恰好是序列的中值，则可以保证处理的区间比上一次减半，由于在一

12、次划分后，只需处理一个子序列，所以，比较次数的递推式是：,最坏情况：每次划分的轴值恰好是序列中的最大值或最小值，则处理区间只能比上一次减少1个，所以，比较次数的递推式是：,平均情况：假设每次划分的轴值是划分序列中的一个随机位置的元素，则处理区间按照一种随机的方式减少，可以证明，算法的平均时间是O(n) 。,2019/3/11,第5章 减治法,Page 28,5.3.1 堆排序,5.3.2 插入排序,5.3 排序问题中的减治法,2019/3/11,第5章 减治法,Page 29,堆的定义 堆是一棵完全二叉树，任一结点关键字小于等于（或大于等于）其孩子结点的关键字。 n个关键字序列K1,K2,Kn

13、称为堆，当且仅当该序列满足： KiK2i且KiK2i+1 (1in/2) 或者 KiK2i且KiK2i+1 (1in/2),小根堆,大根堆,5.3.1 堆排序,2019/3/11,第5章 减治法,Page 30,小根堆,大根堆,不是堆,不是堆,堆中任一棵子树也是堆,2019/3/11,第5章 减治法,Page 31,堆和序列的关系,将堆用顺序存储结构来存储，则堆对应一组序列。,思考：树中的结点与数组下标有什么关系？,若父结点下标为i，则左孩子为2i，右孩子为2i+1； 若某结点下标为i，则其父亲下标为i/2。,2019/3/11,第5章 减治法,Page 32,以结点的编号作为下标，将堆用顺序

14、存储结构（即数组）来存储，则堆对应于一组序列。,5.3.1 堆排序,2019/3/11,第5章 减治法,Page 33,堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。,5.3.1 堆排序,2019/3/11,第5章 减治法,Page 34,为保证时间性能，就要利用已有结果，每次输出堆顶后，剩下元素不是完全重建，应该在原堆上通过某些调整得到； 为保证空间性能，输出的堆顶应利用原有空间，可将它与无序区

15、最后记录交换位置。排序过程中有序区在原记录区的尾部逐步形成并向前扩大，和直接选择排序相反。,两个问题： （1）最初如何由一个无序序列建成一个堆？ （2）在输出堆顶元素后，如何调整剩余元素成为一个新的堆？,1、初始堆的建立,2019/3/11,第5章 减治法,Page 35,把完全二叉树中以每一结点为根的子树都调整为堆。,只有一个结点的树是堆，在完全二叉树中，所有序号in/2的结点都是叶子，以这些结点为根的子树均已是堆。,依次将以序号为n/2，n/21,1的结点作为根的子树都调整为堆。,按该次序调整各结点时，其左、右子树均已是堆。,2019/3/11,第5章 减治法,Page 36,例，对（1,

16、2,9,11,4,6,8,10,16, 5）建初始堆（大根）。 n=10，故从第10/2 5个结点开始进行调整,2019/3/11,第5章 减治法,Page 37,初始大根堆！,2、调整和重建,2019/3/11,第5章 减治法,Page 38,将堆顶元素与堆最后的元素互换； 将其余的元素筛选成堆；,2019/3/11,第5章 减治法,Page 39,堆调整筛选法 关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？,5.3.1 堆排序,2019/3/11,第5章 减治法,Page 40,Ri左、右子树是堆，子树的根为各自子树中关键字最大者， 将Ri和其

17、左、右孩子中关键字最大者放到Ri的位置。 若Ri是三者中的最大，则无需调整，以其为根的子树已是堆； 否则，将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。 交换后以R2i和R2i+1为根的子树可能不再是堆，但其左、右子树仍然是堆，于是重复上述过程，将子树调整为堆，如此逐层递推下去，最多可能一直调整到树叶。 这一过程就像过筛子一样，把较小的关键字筛下去，而将最大关键字一层层地选择上来。,堆调整筛选法,2019/3/11,第5章 减治法,Page 41,大根堆,例:筛选法（大根堆）示例。,2019/3/11,第5章 减治法,Page 42,假设当前要筛选结点的编号为k，堆中最后一个

18、结点的编号为n，并且结点k的左右子树均是堆（即rk+1 rn满足堆的条件），则筛选算法用伪代码可描述为：,时间性能是O(log2n)。,2019/3/11,第5章 减治法,Page 43,2019/3/11,第5章 减治法,Page 44,交换,筛选,交换,筛选,经过跟刚才一样的步骤,堆排序,2019/3/11,第5章 减治法,Page 45,交换,筛选,交换,筛选,2019/3/11,第5章 减治法,Page 46,交换,筛选,交换,筛选,2019/3/11,第5章 减治法,Page 47,交换,筛选,交换,筛选,2019/3/11,第5章 减治法,Page 48,交换,堆排序小结,（1）建

19、堆/堆调整方法： 筛选法：将结点与其孩子结点比较。 （2）堆排序方法： 先建堆； 取出堆顶； 剩下元素再调整为堆； 直至剩下一个元素为止。,2019/3/11,第5章 减治法,Page 49,5.3.2 插入排序,插入排序属于减治法的减一技术,2019/3/11,第5章 减治法,Page 50,每次将无序区第1条记录插入到有序区适当位置。初始取第1条记录为有序区，其它记录为无序区。随着排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。 有序区也可从排序表的尾部生成 。,2019/3/11,第5章 减治法,Page 51,在插入第 i（i1）个记录时，前面

20、的 i-1个记录已经排好序。,（1）如何构造初始的有序序列？ （2）如何查找待插入记录的插入位置?,需解决的关键问题?,2019/3/11,第5章 减治法,Page 52,例：对(49 38 13 76 27 49 )进行插入排序。 初始：（49）38 13 76 27 49 （38 49）13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）,插入排序过程示例,2019/3/11,第5章 减治法,Page 53,r 0 1 2 3 4 5 6,21,18,25,22,

21、10,25*,21,插入排序,22,10,25,18,18,r0的作用?,暂存单元,监视哨,25,2019/3/11,第5章 减治法,Page 54,void InsertSort(int r,int n) /设置监视哨 for(int i=2;i=n;i+)/进行n-1次插入，依次插入 /r2,r3,rn r0=ri; /r0是监视哨 /顺序比较和移动，查找ri的插入位置 for(int j=i-1;r0rj;j-) rj+1=rj; /记录后移，继续向前搜索 rj+1=r0; /插入Ri ,r0为监视哨（Sentinel），省略下标越界检查“j1”：一旦越界，j=01，循环条件r0rj不成

22、立，循环结束。,2019/3/11,第5章 减治法,Page 55,插入排序算法性能分析,最好情况下（正序）：,最坏情况下（逆序或反序）：,时间复杂度为O(n2)。,时间复杂度为O(n)。,2019/3/11,第5章 减治法,Page 56,空间性能：需要一个记录的辅助空间监视哨。 插入排序算法是一种稳定的排序算法。,插入排序算法性能分析,插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。 当待排序的记录个数较多时，大量的比较和移动操作使插入排序算法的效率降低。,2019/3/11,第5章 减治法,Page 57,时间： 最好：正序，n-1趟插入，每趟比较1次，移动0(2

23、)次： Cmin=n-1=O(n)，Mmin=0 最坏：逆序，每趟比较i-1次，移动i-1+2次。 平均： O(n2) 空间：一个辅助空间，用于交换（或监视哨） 。 稳定：相邻元素比较和移动，相等的情况下无需移动。 可用于链表 适用于基本(正向)有序或n较少的情况,2019/3/11,第5章 减治法,Page 58,5.4.1 淘汰赛冠军问题,5.4.2 假币问题,5.4 组合问题中的减治法,2019/3/11,第5章 减治法,Page 59,假设有n=2k个选手进行竞技淘汰赛，最后决出冠军的选手，用函数 bool Comp(string mem1, string mem2); 模拟两位选手的

24、比赛，若mem1获胜则函数Comp返回TRUE ，否则函数Comp返回FALSE，并假定可以在常数时间内完成函数Comp的执行，下面的算法实现选手的竞技淘汰比赛的过程。,5.4.1 淘汰赛冠军问题,2019/3/11,第5章 减治法,Page 60,2019/3/11,第5章 减治法,Page 61,因为n=2k，所以，外层的while循环共执行k次，在每一次执行时，内层的for循环的执行次数分别是n/2，n/4，1，而函数comp可以在常数时间内完成，因此，算法5.8的执行时间为：,2019/3/11,第5章 减治法,Page 62,在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可

25、以通过一架没有刻度的天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个高效的算法来检测出这枚假币。,5.4.2 假币问题,2019/3/11,第5章 减治法,Page 63,问题的解决是经过一系列比较和判断，可以用判定树来描述这个判定过程。 解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。把n枚硬币分成两组，每组有 枚硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。,2019

26、/3/11,第5章 减治法,Page 64,在假币问题中，每次用天平比较后，只需解决一个规模减半的问题，所以，它属于一个减治算法。该算法在最坏情况下的时间性能有这样一个递推式：,应用扩展递归技术求解这个递推式，得到T(n)=O(log2n)。,2019/3/11,第5章 减治法,Page 65,考虑不是把硬币分成两组，而是分成三组，前两组有 组硬币，其余的硬币作为第三组，将前两组硬币放到天平上，如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组的重量不同，则假币一定在较轻的那一组中，用同样的方法对较轻的那组硬币进行处理。显然这个算法存在递推式：,这个递推式的解是

27、T(n)=O(log3n)。,2019/3/11,第5章 减治法,Page 66,考虑假币问题的一个更复杂的版本不知道假币与真币相比较轻还是较重。 设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，从八枚硬币中任取六枚a，b，c，d，e，f，在天平两端各放三枚进行比较。假设a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出现三种比较结果： abcdef abcdef abcdef,2019/3/11,第5章 减治法,Page 67,若abcdef，可以肯定这六枚硬币中必有一枚为假币，同时也说明g，h为真币。这时可将天平两端各去掉一枚硬币，假设去掉c和f，同时将天平两端的

28、硬币各换一枚，假设硬币b，e作了互换，然后进行第二次比较，比较的结果同样可能有三种： aedb：这种情况表明天平两端去掉硬币c，f且硬币b，e互换后，天平两端的轻重关系保持不变，从而说明了假币必然是a，d中的一个，这时我们只要用一枚真币（例如h）和a进行比较，就能找出假币。若ah，则a是较重的假币；若ah，则d为较轻的假币；不可能出现ah的情况。,2019/3/11,第5章 减治法,Page 68, aedb：此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f中，同样用一枚真币（例如h）和c进行比较，若ch，则c是较重的假币；若ch，则f为较轻的假币；不可能出现ch，则b是较重的

29、假币；若bh，则e为较轻的假币；不可能出现bh的情况。,2019/3/11,第5章 减治法,Page 69,2019/3/11,第5章 减治法,Page 70,详见实验课件之 实验四八枚硬币问题,5.5 实验项目八枚硬币问题,2019/3/11,第5章 减治法,Page 71,要点： 1、减治法的基本思想：把一个大问题分解成规模较小的子问题，但这些子问题无需全部求解，而只需求解其中的一个子问题，子问题的解就是原问题的解了，无需对子问题的解进行合并。 2、减治法的基本步骤： （1）划分； （2）求解其中的一个子问题。,本章小结,2019/3/11,第5章 减治法,Page 72,要点： 3、每个问题用减治法怎么解，及时间复杂度是多少。,本章小结,2019/3/11,第5章 减治法,Page 73,P94 习题5 第7题,作业,