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

第 3 章 分治法,概述：算法概要、算法效率 合并排序 快速排序 折半查找 大整数乘法 Strassen 矩阵乘法分治法解凸包,概述,概述（算法概要、算法效率）分治法是著名的通用算法设计技术，很多有效的算法是它的特殊实现。算法思想：解决复杂问题时常从大到小逐步分解问题，求解子问题；然后，合并子问题解，得原问题的解 分而治之 算法概要1.分解原问题为较小规模的子问题（规模最好相同）2.求解子问题“分解求解”常是递归过程，直到子问题可简单求解3.合并子问题的解，得原问题的解。不是所有算法都要“合并”,分治算法概要描述,分治算法的概要描述,集合的模|s|：问题 s 的规模，即 s 集合的元素个数分解尺度 t：求解子问题的规模（不需继续分解）,分治法应用的一个简例,分治法的应用简例 查找最大元素已知：S 有 n 个元素，求 S 的最大元素。不妨设 本题有多种算法，现在用分治法解：每次将 S 一分为二，直到分解到仅 2 个元素的子集为止。,分治法应用简例的过程图解,分治法应用简例的过程图解已知：S=30,11,42,22,1,55,21,43 有 n=23 个元素 求：S 的最大元素,分治法时间效率（例）,分治法的时间效率分析上例的时间效率分析 输入规模：元素个数 n 基本操作：比较操作 效率类别：无最佳、最差、平均效率之分 增长函数：比较次数 T(n)与 n 的关系 求解子集有 2 个元素，需比较 1 次。用数学归纳法分析 n=2=21：T(21)=1 比较 1 次 n=4=22：T(22)=2T(22/2)+1 2T(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 归纳结果：,通用分治递推式及其效率,分治法时间效率的 通用分治递推式 规模 n 的问题，每次分为 a 个子问题，求解子问题规模相等为 n/b（上例 a=2,b=2）。为简化分析，不妨设 n=bk，k=1,2,3,.通用分治递推式 c：求解子集的求解时间（基本操作执行次数）f(n)：子集分解时间+子集解合并时间（本例比较1次 f(n)=1）解递推式，得时间效率主定理：,合并排序,合并排序待排序元素集合一分为二，每个子集继续递归拆分，直到分解到仅一个元素为止。然后，两两合并为一个有序集即完成了排序。过程如下：,合并排序算法,合并排序之分治算法分解,合并排序算法（续）,合并,0 1 2 3 4 5 635407249398049,35,40,72,49,39,80,3540,7249,3980,49,35407249,398049,49 72,35404972,394980,35394049497280,合并排序递归算法演示：,合并排序算法的时间效率分析,合并排序算法的时间效率分析输入规模：元素个数 n 基本操作：比较操作 效率类别：while(i p)and(j q)循环次数与 i、j 有关。最佳情况 每次循环 i 或 j 之一增加，很快达到上限，结束循环。待排序元素已排序，B、C 数组之一很快完成合并。最坏情况 两个循环变量交替增加，循环次数最多。较小元素轮流来自于两个数组。时间效率递推式 通用分治递推式 为简化分析，假定 n=2k,k=1,2,3,.，即 B 和 C 数组元素数相同 每次拆分为两个大小相同的子集，a=b=2,合并排序算法的时间效率分析（续）,现在分析 合并子集解的比较次数，分解过程无基本操作。最差情况：两个循环变量轮流增加，较小元素轮流来自于两个数组 B 或 C。每次合并时B、C 数组元素个数都是 n/2 个，需比较 n1 次：根据分治法效率主定理：,反向替换法可解递推方程（略）,快速排序,快速排序 以非降序为例 算法思想对给定的待排序数组不断进行拆分，这与合并排序对数组的拆分不同。合并排序按元素位置拆分（数组中间），快速排序按元素值大小拆分，得到 分区(Partition)，拆分处称为 分裂点(Split position).递归拆分下去，直到分区仅有一个元素为止。建立分区时完成了元素的重排，拆分结束即排序结束。分区特点：,快速排序算法,分区的确定,两次扫描法确定分区（Partition）AL.R中轴：初选一个元素为中轴 分裂点初值，其他元素与中轴比较 以确定分裂点。选择中轴有多种方法，这里采用简单策略即：选数组第一个元素为中轴：p=AL两次扫描法 从左向右扫描一次，从右向左扫描一次左右：从第 2 个元素开始，逐个与中轴比较，直到遇到大于或等于 中轴的元素为止。（i）左右：从最后一个元素开始，逐个与中轴比较，直到遇到小于或等于 中轴的元素为止。（j）根据两次扫描 i、j 指针是否相交，分三种情况：,未相交（ij）,两次扫描法确定分区(续),AL.R,相交（ij）,AL.R,相交（i=j）,将 i j 和 i=j 两种情况相结合即 i j，就交换 swap AL and Aj得到分裂点 S=j，生成了分区。（生成两个或一个分区）,分划操作Partition演示：,i向右扫描，寻找lilleft的元素,j向左扫描，寻找ljlleft的元素,48,68,72,36,48,12,02,0 1 2 3 4 5 6 7,36不大于等于主元,所以继续扫描,找到大于主元的元素68,扫描暂停;准备和lj交换;,left和right是待排序元素序列的下、上界；,left和right是待排序元素序列的下、上界；,(,),(,),此时,ij,扫描结束;把lleft和lj交换,实现了各元素按“左边小右边大”的原则分布在主元两侧。,如果ij,则交换li和lj,继续各自的扫描。其目的是把较主元小的元素放到左边,较主元大的元素放到右边;,找到小于主元的元素02,准备和li交换;,接下来会分别把主元两侧的两个子序列作为排序对象递归执行快速排序算法(过程略),两次扫描法确定分区的算法伪码,两次扫描法确定分区的算法 Partition(AL.R)pAL/选择中轴 iL+1,jR/左右扫描位置指针。左扫描没找到时，i 停在L+1位置 while(true)while(A i p)and(j L)do jj-1/右扫描 if(ij)then break/左右扫描已交叉，退出循环 swap(A i,A j)/左右扫描未交叉 swap(A L,A j)return(j)/返回分裂点 j,例 15,18,33,10,27,11,13,42,20，请写出快速排序的过程及结果。,结果：10 11 13 1518 20 27 33 42,快速排序算法的时间效率分析,快速排序算法的时间效率分析输入规模：元素个数 n基本操作 比较操作：A i p 效率类别 每次分裂点位置不同，所得两个子分区大小（元素个数）就不同，即子排序问题规模不同，导致子分区排序的基本操作次数不同。因此，快速排序有最佳、最差、平均效率。最佳时间效率 每次分裂都在区域中点，将区域一分为二，得大小相同的两子区域。左右扫描指针交叉时满足 i=j.比较总次数 n 由通用分治递推式和主定理得(a=b=2，n=2k,k 0)：T(1)=0;n 1：T(n)=2T(n/2)+f(n)=nlog2n 建立分区需作 n 次比较，f(n)=n,最差时间效率,最差时间效率 每次分裂都在区域两端，两子区域其一为空，另一个只比原区域少 一个元素 输入序列已排序。例如 A0.n-1 为严格递增：中轴选p=A0，左扫描 i 停在 A1，右扫描 j 停在 A0，左右扫描 交叉，分裂点在 A0，左子区为空，右子区为A1.n-1，共 n+1 次 比较。继续对右子区 A1.n-1 排序，共作 n 次比较；如此继续，直到右子区仅有一个元素为止。T(n)=(n+1)+n+.+3=(n+1)+n+.+3+2+1-2-1=(n+1)(n+2)/2-3(n2)平均时间效率 大小为 n 的随机排列数组，平均比较次数记为 Tavg(n).设分裂点 s(0sn-1)位于每个位置的概率相同为 1/n.两子区的平均比较次数之和为 Tavg(s)+Tavg(n-1-s).,快速排序平均时间效率（续）,平均时间效率递推式：,分裂点 s(0sn-1)在每个位置的概率相等,统计平均,第一趟排序时元素间的比较次数,因此，快速排序的平均情况仅比最佳情况多执行38的比较操作。此外，它的最内层循环效率非常高，因此，比合并排序速度快些。,推导过程如下：,两边同乘以n,用n-1代替式(5-8),用式(5-8)减去式(5-9),两边同除以n(n+1),折半查找,折半查找 以非降序为例算法思想：比较查找键 K 和有序数组中间元素Am K Am 在数组后半部分内查找算法描述,折半查找算法效率,折半查找的算法效率输入规模：元素个数 n基本操作：比较操作效率类别：比较次数与输入元素的分布有关。因此，有最佳、最差、平均效率。最佳效率 Tbest(n)=1最差效率 直接写出比较次数递推式：通过 1次 比较 K=Am，化为一半规模的 1 个子问题 另据通用分治递推式也可得上式：a=1,b=2,f(n)=1 分解问题需作 1 次比较 解递推式（要求自己推导）,折半查找算法简评,折半查找算法简评就键值比较的查找算法而言，折半查找是一种最优的查找算法；折半查找是分治法的一个非常不典型的应用 分治技术是把一个问题分为若干子问题，每个子问题都需分别求解。折半查找只有一个需要求解的子问题，所以，只是退化了的分治法。折半查找法归入减半算法更合适，传统上把它归入分治法。,Strassen 矩阵乘法,Strassen 矩阵乘法 概述改进：计算两个 2 阶方阵的积只需 7 次乘法，蛮力法需 8 次乘法。公式：(1969 年 V.Strassen 发表),简单讨论：经典蛮力法需 8次乘法和 4次加减法，本算法需要 7次乘法和 18次加减法。该算法吸引我们的不是这个原因，而在于当 n 很大时所表现的卓越效率。,Strassen 矩阵乘法时间效率,当 n=2 k，计算两个 n 阶方阵的积 C=AB（若n 不是2 的乘方，矩阵 用全 0 行列填充）。A、B、C 分别划分为 4 个 n/2 阶子矩阵：子矩阵计算式与单个元素一样（替换元素为子矩阵）。例如：C00=M1+M4-M5+M7,其中 M1=(A00+A11)(B00+B11),.n 阶方阵递归分解，直到 n=2 停止分解，计算两个 22 矩阵的积。这就是计算大矩阵乘积的 Strassen 分治法。算法效率输入规模：方阵的阶 n 基本操作：乘法运算效率类别：乘法次数只与方阵的阶 n 有关，无最佳、最差、平均效率,Strassen 矩阵乘法时间效率（续1）,增长函数 n 阶方阵相乘问题，分解为 7个子问题，每个子问题是规模为 n/2 的 子矩阵乘法（M1 M7）。乘法次数递推式：设 n=2k,Strassen 矩阵乘法时间效率（续2）,Strassen 算法的加法效率减少乘法次数是以增加加法次数为代价。所以，检查 Strassen 算法的加法次数增长类型（加法的时间效率）。输入规模：方阵的阶 n基本操作：加法操作（包括减法：带负号的加法）效率类别：与乘法一样，没有最佳、最差、平均效率增长函数递推式 n 阶方阵乘法分解为 7 个n/2 阶矩阵相乘的子问题，作 18 次 n/2 阶 子矩阵加法(n/2)2 次元素加法(子方阵有(n/2)2 个元素)。因此，加法次数的递推式：依据主定理：,实验二 大整数乘法 概述某些应用尤其是当代密码技术，需要对超过100位的十进制整数进行 乘法运算。整数过大超过计算机字长，也需特别处理。经典算法 两个 n 位整数相乘，需 n2 次乘法。将乘法作基本操作，位数 n 作为 输入规模，该蛮力算法具有平方增长率。算法改进 提高效率 策略：减少乘法次数，可适当增加加法次数。举例：计算 2314，要求只作 3 次位乘 23=2101+3100，14=1101+4100，2314=(2101+3100)(1101+4100)=(21)102+(31+24)101+(34)100 4 次乘法 存储 21、34（2 次乘法）的结果：共 3 次乘法 31+24=(2+3)(1+4)-(21)-(34)增加1 次乘法,大整数乘法:算法,两个 2 位数相乘（十进制）两个 n 位数相乘（设 n 为正偶数，a 分为 a1a0 两部分，b 也如此）若 n/2 也是偶数，用同样方法计算 c2,c1,c0。因此，若 n=2k,得到计算 n 位数积的递归算法，当 n=1或足够小时停止。,大整数乘法算法效率,大整数乘法算法效率输入规模：整数位数 n 基本操作：位乘操作效率类别：没有最佳、最差、平均效率增长函数：n 位数乘法问题分解为3个 n/2 位数乘法的子问题，因此 乘法次数 T(n)递推式：（设 n=2k,用反向替换法解）,实验表明：大于600位的整数乘法，分治算法性能超过了经典算法。,