分治法大整数乘法课件.ppt

第3章分治法★概述：算法概要、算法效率★合并排序★快速排序★折半查找★大整数乘法★Strassen矩阵乘法★分治法解凸包概述★概述（算法概要、算法效率）分治法是著名的通用算法设计技术，很多有效的算法是它的特殊实现。算法思想：解决复杂问题时常从大到小逐步分解问题，求解子问题；然后，合并子问题解，得原问题的解——分而治之算法概要1.分解原问题为较小规模的子问题（规模最好相同）2.求解子问题——“分解－求解”常是递归过程，直到子问题可简单求解3.合并子问题的解，得原问题的解。不是所有算法都要“合并”原问题S子问题S1子问题S2……子问题SkS1的解S2的解……Sk的解问题S的解分治算法概要描述分治算法的概要描述1212//(){(||)(){,,1{}(,,)}}//(////)iikkDivideandConquerstadhocerysdivideintosmallersubsetsssifthenelsefortodskyoretDivideansimergdConquekeursyyyrn子集求解个子集递归分解合并算法集合的模|s|：问题s的规模，即s集合的元素个数分解尺度t：求解子问题的规模（不需继续分解）分治法应用的一个简例分治法的应用简例——查找最大元素已知：S有n个元素，求S的最大元素。不妨设本题有多种算法，现在用分治法解：每次将S一分为二，直到分解到仅2个元素的子集为止。2,0,1,2,...mnm1121211222(){2(||)(,){,||||||/2()()(//DivideandConquerSearchMaxStStmaxssdivideintotwosmallersubsetSSSmaxDivideandConquerSearchifthenreturnelsereturnMaxmaxDivideandConquerSearchMaxSSandSSSmax子集求解12,)/}}/maxmax合并算法分治法应用简例的过程图解分治法应用简例的过程图解已知：S={30,11,42,22,1,55,21,43}有n=23个元素求：S的最大元素30,11,42,22{,1,55,21,43}S(1)130,{,4212}1,2S(1)21,5{,251,43}S(2)1{30,11}S(2)2{42,22}S(2)1{1,55}S(2)2{21,43}S(2)130max(2)242max(2)155max(2)243max(1)142max(1)255max55max分治法时间效率（例）分治法的时间效率分析上例的时间效率分析输入规模：元素个数n基本操作：比较操作效率类别：无最佳、最差、平均效率之分增长函数：比较次数T(n)与n的关系求解子集有2个元素，需比较1次。用数学归纳法分析——①n=2=21：T(21)=1——比较1次②n=4=22：T(22)=2T(22/2)+12T(4/2)：子集数=2，规模=4/2+1：两个子集解需要合并1次（比较1次）③n=8=23：T(23)=2T(23/2)+1=2T(23-1)+1④n=2k：T(2k)=2T(2k/2)+1=2T(2k-1)+1归纳结果：1,2()2(/2)1,2knTnTnn通用分治递推式及其效率分治法时间效率的通用分治递推式规模n的问题，每次分为a个子问题，求解子问题规模相等为n/b（上例a=2,b=2）。为简化分析，不妨设n=bk，k=1,2,3,...通用分治递推式——c：求解子集的求解时间（基本操作执行次数）f(n)：子集分解时间+子集解合并时间（本例比较1次f(n)=1）解递推式，得时间效率主定理：()(/)()ntTnaTnbcfnntlog()()(log)()bddddadnabTnnnabnab()(),dfnnd0设1,2,0abc合并排序★合并排序待排序元素集合一分为二，每个子集继续递归拆分，直到分解到仅一个元素为止。然后，两两合并为一个有序集即完成了排序。过程如下：83267154832683268338262623687154715471175445145712345678合并排序算法合并排序之分治算法分解[0...1][0.../21][/2..[0.../21][0.../.1],,2]/////(){(1){()()()}/////}AnAnAnMergeSortifncopytocopytoMergeSortMergeSortMBnCnBCnCArgBee新生成两个临时数组B、C递归拆分递归拆分合并B,CA分解过程无基本操作合并排序算法（续）合并([0...],[0...],[0...]){0,0,0()[][],1[][],11()[][...//1]111.[][].//,,.1BCAandBiCjMergeijkwhiledoifAkBiiielseAkCjjijkjkkifcopyCtoApqelspqpqipjqikpjecpqo等号的作用？指向下一个元素[][...1}...1]yBtoAkpiqpijk0123456[35407249398049][35][40][72][49][39][80][3540][7249][3980][49][35407249][398049][4972][35404972][394980][35394049497280]合并排序递归算法演示：合并排序算法的时间效率分析合并排序算法的时间效率分析输入规模：元素个数n基本操作：比较操作效率类别：while(ip)and(jq)循环次数与i、j有关。最佳情况——每次循环i或j之一增加，很快达到上限，结束循环。待排序元素已排序，B、C数组之一很快完成合并。最坏情况——两个循环变量交替增加，循环次数最多。较小元素轮流来自于两个数组。时间效率递推式——通用分治递推式为简化分析，假定n=2k,k=1,2,3,...，即B和C数组元素数相同——每次拆分为两个大小相同的子集，a=b=2[][]BiCj1()20,(),(/2)1MergefnTnTnnn()(),dfnnd0若,不用解递推式，用定理得效率类型合并排序算法的时间效率分析（续）现在分析——合并子集解的比较次数，分解过程无基本操作。最差情况：两个循环变量轮流增加，较小元素轮流来自于两个数组B或C。每次合并时B、C数组元素个数都是n/2个，需比较n–1次：根据分治法效率主定理：()Mergefn1()1(),1Mergefnnnd1:()2(/2)(1)nTnTnn2,()(log)1,ddabdaTnnnb反向替换法可解递推方程（略）快速排序★快速排序——以非降序为例算法思想对给定的待排序数组不断进行拆分，这与合并排序对数组的拆分不同。合并排序按元素位置拆分（数组中间），快速排序按元素值大小拆分，得到分区(Partition)，拆分处称为分裂点(Splitposition).递归拆分下去，直到分区仅有一个元素为止。建立分区时完成了元素的重排，拆分结束即排序结束。分区特点：[][][0]...[1][1]...[[]1]PartitionPartitiAAosnsAAsAsAnAs无序的无序的分裂点快速排序算法//([...])//([]){()([...])([.....1:.//////}1.])falseLRonlyoneelementSisasplitpositionQuickSortAifLRQuickSortALQuickSSPartitileftpartitionrightpartitonALioRnortARSLRS关键是分区函数Partition[][][0]...[1][1]...[[]1]PartitionPartitiAAosnsAAsAsAnAs分区的确定两次扫描法确定分区（Partition）A[L...R]中轴：初选一个元素为中轴——分裂点初值，其他元素与中轴比较以确定分裂点。选择中轴有多种方法，这里采用简单策略即：选数组第一个元素为中轴：p=A[L]两次扫描法——从左向右扫描一次，从右向左扫描一次左→右：从第2个元素开始，逐个与中轴比较，直到遇到大于或等于中轴的元素为止。（i→）左←右：从最后一个元素开始，逐个与中轴比较，直到遇到小于或等于中轴的元素为止。（←j）根据两次扫描i、j指针是否相交，分三种情况：......≥p...＞p≤p＜p...pA[L...R]ij两次扫描法确定分区(续)p...≤p≤p≥p≥p...A[L...R]ijp...≤p=p≥p≥p...A[L...R]ij将ij和i=j两种情况相结合即i≥j，就交换swapA[L]andA[j]得到分裂点S=j，生成了分区。（生成两个或一个分区）分划操作Partition演示：i向右扫描，寻找l[i]≥l[left]的元素j向左扫描，寻找l[j]≤l[left]的元素48687236481202leftrightij∞0123456736不大于等于主元,所以继续扫描找到大于主元的元素68,扫描暂停;准备和l[j]交换;left和right是待排序元素序列的下、上界；left和right是待排序元素序列的下、上界；()()此时,ij,扫描结束;把l[left]和l[j]交换,实现了各元素按“左边小右边大”的原则分布在主元两侧。如果ij,则交换l[i]和l[j],继续各自的扫描。其目的是把较主元小的元素放到左边,较主元大的元素放到右边;找到小于主元的元素02,准备和l[i]交换;接下来会分别把主元两侧的两个子序列作为排序对象递归执行快速排序算法(过程略)两次扫描法确定分区的算法伪码两次扫描法确定分区的算法Partition(A[L...R]){p←A[L]//选择中轴i←L+1,j←R//左右扫描位置指针。左扫描没找到时，i停在L+1位置while(true){while(A[i]p)and(i≤R)doi←i+1//左扫描while(A[j]p)and(j≥L)doj←j-1//右扫描if(i≥j)thenbreak//左右扫描已交叉，退出循环swap(A[i],A[j])//左右扫描未交叉}swap(A[L],A[j])return(j)//返回分裂点j}例﹕15,18,33,10,27,11,13,42,20，请写出快速排序的过程及结果。键值步骤[0][1][2][3][4][5][6][7][8]pass1：[101311]15[2733184220]pass2：10[1311]15[2733184220]pass3：10[11]1315[2733184220]pass4：10111315[1820]27[4233]pass5：1011131518[20]27[4233]pass6：10111315182027[33]42结果：101113151820273342快速排序算法的时间效率分析快速排序算法的时间效率分析输入规模：元素个数n基本操作比较操作：A[i]p和A[j]p效率类别每次分裂点位置不同，所得两个子分区大小（元素个数）就不同，即子排序问题规模不同，导致子分区排序的基本操作次数不同。因此，快速排序有最佳、最差、平均效率。最佳时间效率每次分裂都在区域中点，将区域一分为二，得大小相同的两子区域。左右扫描指针交叉时满足i=j.比较总次数n由通用分治递推式和主定理得(a=b=2，n=2k,k0)：T(1)=0;n1：T(n)=2T(n/2)+f(n)=nlog2n建立分区需作n次比较，f(n)=n最差时间效率最差时间效率每次分裂都在区域两端，两子区域其一为空，另一个只比原区域少一个元素——输入序列已排序。例如