算法分析第四章.ppt

第四章分治法 用五个特性判断是否是一个算法 二元比较树-顺序检索 　n个元素存在如下关系的:A(1)A(2)…A(n),检索一给定元素x是否在A中出现 二元比较树-二分检索 4.4 归并分类 讨论： 1. 可以消去递归，取消栈的使用，例如： ① 采用由底向上的方法，将元素两两配对； ② 自然合并排序法； 2. 空间代价 3. 适合于并行计算，采用并行或专用集成电路实现数据排序操作时，派生出许多算法，例如奇偶合并排序，双调合并排序等。 对3个关键字分类的二元比较树 小结 一般方法 二分检索 归并分类 斯特拉森矩阵乘法 侧重算法设计和算法分析 作业： 2, 3, 5, 7, 11, 12, 23 元素A(i)和A(j)的比较与i和j的比较时间相差不大时，过程MAXMIN不可取。 设MAXMIN的频率计数为C(n)，n=2k , k为整数, 当n2时, 有: C(n)=5n/2-3 4.3 找最大和最小元素 C(n)= 2C(n/2)+3 = 2(2C(n/4)+3)+3 = 4C(n/4)+6+3 …… = 2k-1C(2)+3*( 2k-2 +2k-3+…+22+21+20 ) =2k+3*(2k-1-1) =2k+3*2k-1-3 =5n/2-3 2 n=2 C(n)= 2C( n/2 )+ 3 n2 直接算法的比较次数为2(n-1), 加上实现for循环 需要的比较次数, 则为3(n-1), 虽然3(n-1)略大于 5n/2-3, 但MAXMIN算法还有递归所带来的时间 开销, 这种情况下直接算法要快一些 结论: 如果数组A的元素之间的比较远比整型变量的比较代价昂贵，则分治法产生效率较高的算法；反之则得到一个效率较低的程序。 4.3 找最大和最小元素 直接方法(插入法) for j?2 to n do 将A(j)放入已分类集合A(1:j?1) repeat 4.4 归并分类 问题描述: 给定一个含有n个元素的集合， 把它们按一定的次序分类(如非降次序) procedure INSERTIONSORT(A, n) A(0) ? ?? for j ? 2 to n do item ? A(j); i ? j?1; while ( itemA(i)) do A(i+1) ? A(i); i?i?1; repeat A(i+1) ? item; repeat end INSERTIONSORT 插入分类算法描述 数组元素的比较和移动 将本次考虑的元素 插入相应位置 可能执行0~j次(j=2,3…n) 最好情况? (n) 最坏情况的计算时间：2+…+n=(n(n+1)/2)?1=?(n2) 用item保存当前元素值 4.4 归并分类 分：平均分为2个子集合 治：递归调用分类算法，将2个子集合分类 合：将2个分类的子集合并为一个分类集合 4.4 归并分类 分治策略设计归并分类算法 递归调用，分别对分解出来的两个子问题排序 合并两个已排好的序列，得到原问题的解 归并排序算法描述 Procedure MERGESORT(low,high) int low, high, mid; if (lowhigh) then mid ? ?(low+high)/2? call MERGESORT(low,mid) call MERGESORT(mid+1,high) call MERGE(low,mid,high) end MERGESORT 4.4 归并分类 合并函数MERGE的算法描述 procedure MERGE(low, mid, high) int h,i,j, k, low, mid, high; global A(low : high); local B(low : high); h ? low; i? low; j? mid+1; while (h?mid and j?high) do if (A(h) ?A(j)) then { B(i) ? A(h); h ? h+1; } else { B(i) ? A(j); j ? j+1;