《天津科技大学算法设计与分析第5章减治法》由会员分享，可在线阅读，更多相关《天津科技大学算法设计与分析第5章减治法（41页珍藏版）》请在金锄头文库上搜索。
1、2019/2/22,算法设计与分析-减治法,1,第5章 减治法,5.1 减治法的设计思想,5.2 查找问题中的减治法,5.3 排序问题中的减治法,5.4 组合问题中的减治法,2019/2/22,算法设计与分析-减治法,2,5.1 减治法的设计思想,规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系： （1）原问题的解只存在于其中一个较小规模的子问题中； （2）原问题的解与其中一个较小规模的解之间存在某种对应关系。,由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。,2019/2/22,算法设计与分析-减治法,3
2、,减治法的设计思想,2019/2/22,算法设计与分析-减治法,4,例：计算an的值，应用减治技术得到如下计算方法：,应用分治法得到an的计算方法是：,O (log2n),O (nlog2n),2019/2/22,算法设计与分析-减治法,5,应用减治法处理问题的效率一般是O(log2n)数量级。,减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：,2019/2/22,算法设计与分析-减治法,6,5.2 查找问题中的减治法,5.2.1 折半查找,5.2.2 二叉查找树,2019/2/22,算法设计与分析-减治法,7,基本思想：在有序表中，取中
3、间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,5.2.1 折半查找,2019/2/22,算法设计与分析-减治法,8,例：查找值为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/2/22,算法设计与分析-减治法,9,2019/2/22,
4、算法设计与分析-减治法,10,判定树描述折半查找的判定过程。 长度为n的判定树的构造方法为： （1）当n=0时，判定树为空； （2）当n0时，判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r1 rmid-1相对应的判定树，根结点的右子树是与rmid+1 rn相对应的判定树。,2019/2/22,算法设计与分析-减治法,11,具有11个结点的判定树,在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有n个结点的判定数的深度为 。,2019/2/22,算法设计与分析-减治法,12,5.2.2 二叉
5、查找树,由二叉排序树的定义，在二叉排序树root中查找给定值k的过程是： 若root是空树，则查找失败； 若k根结点的值，则查找成功； 否则，若k根结点的值，则在root的左子树上查找； 否则，在root的右子树上查找； 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。 二叉排序树的查找效率就在于只需要查找两个子树之一。,2019/2/22,算法设计与分析-减治法,13,2019/2/22,算法设计与分析-减治法,14,二叉排序树的结点结构为： struct BiNode int data; /结点的值，假设查找集合的元素为整型 BiNode *lchild,
6、 *rchild; /指向左、右子树的指针 ;,2019/2/22,算法设计与分析-减治法,15,在二叉排序树上查找关键码等于给定值的结点的过程，恰好走了一条从根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数最少为1次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。,具有n个结点的二叉树的深度至少是 ，至多是n，所以，二叉排序树的查找性能在O(log2n)和O(n)之间。,2019/2/22,算法设计与分析-减治法,16,5.3 排序问题中的减治法,5.3.1 堆排序,5.3.2 选择问题,2019/2/22,算法设计与分析-减治法,17,5
7、.3.1 堆排序,以结点的编号作为下标，将堆用顺序存储结构（即数组）来存储，则堆对应于一组序列。,2019/2/22,算法设计与分析-减治法,18,堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。,2019/2/22,算法设计与分析-减治法,19,堆调整问题：将一个无序序列调整为堆 （1）筛选法调整堆 关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？,20
8、19/2/22,算法设计与分析-减治法,20,假设当前要筛选结点的编号为k，堆中最后一个结点的编号为n，并且结点k的左右子树均是堆（即rk+1 rn满足堆的条件），则筛选算法用伪代码可描述为：,时间性能是O(log2n)。,2019/2/22,算法设计与分析-减治法,21,2019/2/22,算法设计与分析-减治法,22,（2）插入法调整堆 关键问题是：在堆中插入一个结点，如何调整被插入结点，使整个完全二叉树仍然是一个堆？,2019/2/22,算法设计与分析-减治法,23,假设当前堆中有k个结点，则要插入结点的编号为k+1，插入法调整堆的算法如下：,时间复杂性为O(log2n)。,2019/2
9、/22,算法设计与分析-减治法,24,2019/2/22,算法设计与分析-减治法,25,设无序序列 T =(r1, r2, , rn)，T 的第k（1kn）小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找 T 的第k小元素的问题称为选择问题。,5.3.2 选择问题,特别地，将寻找第n/2小元素的问题称为中值问题。,2019/2/22,算法设计与分析-减治法,26,（1）若k=s，则rs就是第k小元素； （2）若ks，则第k小元素一定在序列rs+1 rj中；,考虑快速排序中的划分过程，一般情况下，设待划分的序列为ri rj，选定一个轴值将序列ri rj进行划分，使
10、得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则：,2019/2/22,算法设计与分析-减治法,27,选择问题的例子:,2019/2/22,算法设计与分析-减治法,28,2019/2/22,算法设计与分析-减治法,29,最好情况：每次划分的轴值恰好是序列的中值，则可以保证处理的区间比上一次减半，由于在一次划分后，只需处理一个子序列，所以，比较次数的递推式是：,最坏情况：每次划分的轴值恰好是序列中的最大值或最小值，则处理区间只能比上一次减少1个，所以，比较次数的递推式是：,平均情况：假设每次划分的轴值是划分序列中的一个随机位置的元素，则处理区间按照一种
11、随机的方式减少，可以证明，算法的平均时间是O(n) 。,2019/2/22,算法设计与分析-减治法,30,5.4 组合问题中的减治法,5.4.1 淘汰赛冠军问题,5.4.2 假币问题,2019/2/22,算法设计与分析-减治法,31,5.4.1 淘汰赛冠军问题,假设有n=2k个选手进行竞技淘汰赛，最后决出冠军的选手，用函数 bool Comp(string mem1, string mem2); 模拟两位选手的比赛，若mem1获胜则函数Comp返回TRUE ，否则函数Comp返回FALSE，并假定可以在常数时间内完成函数Comp的执行，下面的算法实现选手的竞技淘汰比赛的过程。,2019/2/2
12、2,算法设计与分析-减治法,32,2019/2/22,算法设计与分析-减治法,33,因为n=2k，所以，外层的while循环共执行k次，在每一次执行时，内层的for循环的执行次数分别是n/2，n/4，1，而函数comp可以在常数时间内完成，因此，算法5.8的执行时间为：,2019/2/22,算法设计与分析-减治法,34,5.4.2 假币问题,在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个高效的算法来检测出这枚假币。,2019/2/22,算法设计与分析-减治法,
13、35,问题的解决是经过一系列比较和判断，可以用判定树来描述这个判定过程。,解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。把n枚硬币分成两组，每组有 枚硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。,如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。,2019/2/22,算法设计与分析-减治法,36,在假币问题中，每次用天平比较后，只需解决一个规模减半的问题，所以，它属于一个减治算法。该算法在最坏情况下的时间性能有这样一个递推式：,应用扩展递归技术求解这个递推式，得到T(n)=O(lo
14、g2n)。,2019/2/22,算法设计与分析-减治法,37,考虑不是把硬币分成两组，而是分成三组，前两组有 组硬币，其余的硬币作为第三组，将前两组硬币放到天平上，如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组的重量不同，则假币一定在较轻的那一组中，用同样的方法对较轻的那组硬币进行处理。显然这个算法存在递推式：,这个递推式的解是T(n)=O(log3n)。,2019/2/22,算法设计与分析-减治法,38,考虑假币问题的一个更复杂的版本不知道假币与真币相比较轻还是较重。,设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，从八枚硬币中任取六枚a，b，c，
15、d，e，f，在天平两端各放三枚进行比较。,假设a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出现三种比较结果： abcdef abcdef abcdef,2019/2/22,算法设计与分析-减治法,39,若abcdef，可以肯定这六枚硬币中必有一枚为假币，同时也说明g，h为真币。这时可将天平两端各去掉一枚硬币，假设去掉c和f，同时将天平两端的硬币各换一枚，假设硬币b，e作了互换，然后进行第二次比较，比较的结果同样可能有三种：, aedb：这种情况表明天平两端去掉硬币c，f且硬币b，e互换后，天平两端的轻重关系保持不变，从而说明了假币必然是a，d中的一个，这时我们只要用一枚真币（例如h）和a进行比较，就能找出假币。若ah，则a是较重的假币；若ah，则d为较轻的假币；不可能出现ah的情况。,2019/2/22,算法设计与分析-减治法,40, aedb：此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f中，同样用一枚真币（例如h）和c进行比较，若ch，则c是较重的假币；若ch，则f为较轻的假币；不可能出现ch的情况。, aeh，则b是较重的假币；若bh，则e为较轻的假币；不可能出现bh的情况。,2019/2/22,算法设计与分析-减治法,41,
