14章分治法-2016摘要.pptx

14 章 分治法; 提 纲;14.1 分治法思想 ;Reminder: master method;适用条件;步骤;例14-0 [找出伪币];问题: 计算 an, 其中 n∈N. Naive algorithm: Θ(n).;;例14-2 [金块问题] ;直接求解2：;分治法求解;例14-2 [金块问题]（续）;程序14-1 找出最小值和最大值的非递归程序;程序14-1 找出最小值和最大值的非递归程序;程序14-1 找出最小值和最大值的非递归程序;算法分析;例14.3 大整数的乘法;算法改进;更快的方法;例14-4 [矩阵乘法];;;;;;;Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。 Best to date (of theoretical interest only): Θ(n2.376) (Don Coppersmith, Shmuel Winograd, Matrix Multiplication via Arithmetic Progressions, STOC 1987: 1-6). 是否能找到O(n2)的算法？目前为止还没有结果。;;14.2应用;残缺棋盘问题;不同方向的三格板;Defective Chessboard;;;Defective Chessboard;14.2.2 归并排序 ;例14.5;图14-6 分治排序算法的伪代码;算法复杂度;算法复杂度（续1）;14.2.3 快速排序 ;对n个元素进行快速排序 1.分：将n个元素在支点x分成两个子序列，支点左边元素都小于等于支点元素，右边元素都大于等于支点元素 2.治：递归的对两个字序列使用快速排序算法 3. 归并：将已排好序的子序列归并;;平均情形分析;平均情形分析;平均情形分析;图14-10 各种排序算法的比较;图14-12 各排序算法平均时间的曲线图 ;14.2.4 选择问题;;中间的中间规则;;;例14-6 [中间的中间];定理14-2;;;;14.2.5 距离最近的点对;给定;一维空间中的情形;二维空间中的最近点对问题;二维空间中的最近点对问题;二维空间中的最近点对问题;二维空间中的最近点对问题;二维空间中的最近点对问题;14.4 复杂性的上限、下限 ;复杂性的下限;比较算法;14.4.1 最小最大问题的下限;状态空间方法;Max-min问题的状态空间;证明（过程）;证明（过程续1）;;证明（过程续2）;;证明（总结）;14.4.2排序算法的下限;14.4.2 排序算法的下限;图14-19 n=3 时InsertionSort 的决策树;对图14-19证明过程 的说明;决策树说明;结论;补充思考题：逆序对问题;习题：