Algorithms Chapter 3 蛮力法.pptVIP

* * * * * * * * * * * * * * Deng Xin The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms 算法分析与设计Analysis and Design of Computer Algorithms 第三章 蛮力法 Brute Force 蛮力法 就像宝剑不是撬棍一样，科学也很少使用蛮力。——Edward Lytton 认真做事常常是浪费时间。——Robert Byrne 蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。 * 蛮力法的优点 可以用来解决广阔领域的问题 对于一些重要的问题，它可以产生一些合理的算法 解决问题的实例很少时，它让你花费较少的代价 可以解决一些小规模的问题 可以作为其他高效算法的衡量标准 * 教学内容 选择排序和冒泡排序 顺序查找和蛮力字符串匹配 最近对和凸包问题的蛮力算法 穷举查找 要求 掌握蛮力法的基本思想，掌握排序和查找问题的蛮力算法。 * 选择排序 (p76) A[min] 基本操作“比较”的执行次数： 以第一个元素为基准，找到最小的元素，交换位置，然后以第二个为基准…… * 冒泡排序 算法 BubbleSort(A[0..n-1]) //该算法用冒泡排序对数组A[0..n-1]排序 //输入：一个可排序的数组A //输出：非降序排列的数组 for i?0 to n-2 do for j?0 to n-2-i do if A[j+1]A[j] swap A[j] and A[j+1] 第一遍把最大元素沉到最后位置，第二遍把第二大元素沉下去…… * 顺序查找 如果是有序表，则只需要找到一个大于或等于查找键的元素，算法就可以终止。 查找键做“限位器”：避免每次while循环中都检查 i 是否到了表的末尾。 * 蛮力字符串匹配 * 蛮力字符串匹配 – 例子: 如果文本的长度是n，模式的长度是m；最坏情况可能做n-m+1次模式匹配（例：n=6,m=3）的尝试，而1次模式匹配尝试在最坏情况下会做m次比较(最后一个字符不匹配)。所以，最坏情况下的算法效率属于Θ(nm)。 * 更多的蛮力算法例子:最近对 问题: 在k-维空间中的n个点中，找距离最近的点对； 蛮力算法: 计算每对点之间的距离； 效率: * 最近对问题 // 约束ij，从而避免同一对点被比较两次。 不过不开平方根，只比较(xi-xj)2+(yi-yj)2 ，则算法得到简化。平方操作执行次数： * 更多的蛮力算法例子:凸包 问题: 对于平面上n个点，找包围它们的最小凸多边形； * 凸包问题 定义 对于平面上的一个点集合（有限或无限），如果以集合中任意两点P和Q为端点的线段都属于这个集合，则这个集合是凸的。 定义 一个点集合S的凸包是包含S的最小凸集合。 蛮力算法: 想象，用橡皮筋去套一圈钉子 * 更多的蛮力算法例子:凸包 问题: 对于平面上n个点，找包围它们的最小凸多边形； 蛮力算法: 对于每对点 p1和p2 ，判断是否所有其他点都在连接 p1和p2 的直线的同一侧； 效率: * 凸包问题 定理 任意包含n2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形。 凸包问题是为一个n个点的集合构造凸包的问题。 极点：对于任何一集合中的点为端点的线段来说，它们不是这种线段的中点。 对于一