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

《分治法大整数乘法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章分治法概述：算法概要、算法效率合并排序快速排序折半查找大整数乘法Strassen矩阵乘法分治法解凸包概述概述（算法概要、算法效率）分治法是著名的通用算法设计技术，很多有效的算法是它的特殊实现。算法思想：解决复杂问题时常从大到小逐步分解问题，求解子问题；然后，合并子问题解，得原问题的解——分而治之算法概要1.分解原问题为较小规模的子问题（规模最好相同）2.求解子问题——“分解－求解”常是递归过程，直到子问题可简单求解3.合并子问题的解，得原问题的解。不是所有算法都要“合并”原问题S子问题S1子问题S2……子问题SkS1的解S2的解……Sk的解问题S的解分治算法概要描述分治算法的

2、概要描述集合的模

3、s

4、：问题s的规模，即s集合的元素个数分解尺度t：求解子问题的规模（不需继续分解）分治法应用的一个简例分治法的应用简例——查找最大元素已知：S有n个元素，求S的最大元素。不妨设本题有多种算法，现在用分治法解：每次将S一分为二，直到分解到仅2个元素的子集为止。分治法应用简例的过程图解分治法应用简例的过程图解已知：S={30,11,42,22,1,55,21,43}有n=23个元素求：S的最大元素分治法时间效率（例）分治法的时间效率分析上例的时间效率分析输入规模：元素个数n基本操作：比较操作效率类别：无最佳、最差、平均效率之分增长函数：比较次数T(n)与n的关系求解子

5、集有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归纳结果：通用分治递推式及其效率分治法时间效率的通用分治递推式规模n的问题，每次分为a个子问题，求解子问题规模相等为n/b（上例a=2,b=2）。为简化分析，不妨设n=bk，k=1,2,3,...通用分治递推式——c：求解子集的求解时间

6、（基本操作执行次数）f(n)：子集分解时间+子集解合并时间（本例比较1次f(n)=1）解递推式，得时间效率主定理：合并排序合并排序待排序元素集合一分为二，每个子集继续递归拆分，直到分解到仅一个元素为止。然后，两两合并为一个有序集即完成了排序。过程如下：合并排序算法合并排序之分治算法分解合并排序算法（续）合并0123456[35407249398049][35][40][72][49][39][80][3540][7249][3980][49][35407249][398049][4972][35404972][394980][35394049497280]合并排序递归算法演示：合并

7、排序算法的时间效率分析合并排序算法的时间效率分析输入规模：元素个数n基本操作：比较操作效率类别：while(i

8、变量轮流增加，较小元素轮流来自于两个数组B或C。每次合并时B、C数组元素个数都是n/2个，需比较n–1次：根据分治法效率主定理：反向替换法可解递推方程（略）快速排序快速排序——以非降序为例算法思想对给定的待排序数组不断进行拆分，这与合并排序对数组的拆分不同。合并排序按元素位置拆分（数组中间），快速排序按元素值大小拆分，得到分区(Partition)，拆分处称为分裂点(Splitposition).递归拆分下去，直到分区仅有一个元素为止。建立分区时完成了元素的重排，拆分结束即排序结束。分区特点：无序的无序的分裂点快速排序算法分区的确定两次扫描法确定分区（Partition）A[L..

9、.R]中轴：初选一个元素为中轴——分裂点初值，其他元素与中轴比较以确定分裂点。选择中轴有多种方法，这里采用简单策略即：选数组第一个元素为中轴：p=A[L]两次扫描法——从左向右扫描一次，从右向左扫描一次左→右：从第2个元素开始，逐个与中轴比较，直到遇到大于或等于中轴的元素为止。（i→）左←右：从最后一个元素开始，逐个与中轴比较，直到遇到小于或等于中轴的元素为止。（←j）根据两次扫描i、j指针是否相交，分三种情况：......≥p...＞p≤p＜p...pA[L...R