计算机算法设计与分析4第四章分治法.ppt

* 首先调用QUICKSORT(1,7) //low?1, high?7 if 1?7 then { j?8; call PARTITION(1, 8); call QUICKSORT(low, j ?1) call QUICKSORT(j+1, high) } end QUICKSORT 快速分类实例分析过程(I) 等PARTITION(1, 8)调用结束后,返回参数j的值，才能执行递归调用 PARTITION(m, p) //m?1, p?8 t?A[m]?5; i?m?1; loop(第1次) loop i?? until A[i]?t ; i?3 loop p? ? until A[p]?t ; p?6 if (i?p) then A[i]? A[p]; A[1] A[2] A[3] A[4] A[5] A[6] A[7] 5 3 9 2 7 1 8 A[1] A[2] A[3] A[4] A[5] A[6] A[7] 5 3 1 2 7 9 8 * A[m]?A[p]; 即A[1]?A[4]?2 A[p]?t; 即A[4]?5 end // p?4的值带回 loop(第2次,i?3, p?6) loop i?? until A[i]?t ; i?5 loop p? ? until A[p]?t ; p?4 if (i≮p) 执行else exit loop1 A[1] A[2] A[3] A[4] A[5] A[6] A[7] 5 3 1 2 7 9 8 A[1] A[2] A[3] A[4] A[5] A[6] A[7] 2 3 1 5 7 9 8 递归调用 QUICKSORT(low, j?1) 即QUICKSORT(1, 3) 递归调用 QUICKSORT(j?1,high) 即QUICKSORT(5, 7) 快速分类实例分析过程(II) * 快速分类算法的分析 I ：时间复杂性 假设前提 互不相同；随机选取划分元素 划分单元随机选取的改进 快速分类的性能取决于划分的对称性！ 随机选取更合理，因为最好能找到中间元素 最坏情况下： 划分算法比较次数为元素数：p?m ?1 第i级的比较次数：n?i?1 (实际上是固定的) 最坏情况下级数为n?1(每次取最小或最大值） 总和：n+(n?1)+?= O(n2) 平均情况下： 划分元素最终位置机会均等， 运用概率公式得： * 快速分类算法的分析 II ：栈空间使用 递归算法：最坏情况下 ?(n) 改进的迭代算法： 每次选择小的文件继续处理（较小的文件在处理过程中相对迭代次数少，可能产生的栈空间占用少）?(logn) 归并分类和快速分类算法的比较 * 选择问题定义 算法4.15 举例 分析： 最坏情况下：?(n2) 平均情况下：?(n) 4.6 选择问题 * * 构造最坏情况下?(n)的选择算法 二次中间值规则 粗略算法4.16 分析 Select2的实现 * 4.7 斯特拉森矩阵乘法 传统方法及计算时间 斯特拉森矩阵乘法及计算时间 * A和B的乘积矩阵C中的元素C(i,j)定义为:　 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C(i, j)，需要做n次乘法和n?1次加法。因此，计算出矩阵C中的 n2个元素所需的计算时间为O(n3) 传统方法及计算时间 * 斯塔拉森算法的实现基础 假定A和B的级数n是2的幂，否则，添加适当的全零行和全零列，使其变成级是2的幂的方阵。 将A和B都分成4个(n?2)?(n?2)的方形矩阵，于是A和B就可以看成是两个以(n?2)?(n?2)矩阵为元素的2?2矩阵。 1969年，斯特拉森(V. Strassen)利用分治策略并加上一些处理技巧，设计出一种矩阵乘法。他所设计的算法的计算时间是O(n2.81)。 * 将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为： 由此可得： 复杂度分析 一般分治法的实现思想 * 复杂度分析 T(n)=?(n3) 乘法次数较多导致算法的计算时间数量级没有降低。斯特拉森在分治法的基础上使用一种减少乘法次数而让加减法次数相应增加的处理方法来计算Cij。 一般分治法复杂度分析 * 斯塔拉森算法的实现思想 (1)用7个乘法和10个加(减)法来算出下面7个(n?2)?(n?2)矩阵。 (2)用8个加(减)法算出这些Cij。 复杂度分析 T(n)=?(nlog7) =?(n2.81)?较大的改进 * 传统方法