文章目录一、蛮力法的设计思想一基本概念二时间性能三关键——依次处理所有元素四用途二、查找问题中的蛮力法一顺序查找二串匹配问题1.问题描述2.BF算法1如何实现2时间复杂度3.KMP算法改进的模式匹配算法1BF低效原因2设计思想三、排序问题中的蛮力法一选择排序1.基本思想2.实例3.时间复杂度二冒泡排序1.基本思想2.时间复杂度四、图问题中的蛮力法一哈密顿回路1.问题描述2.基本思想3.时间复杂度二TSP问题1.问题描述2.时间复杂度一、蛮力法的设计思想一基本概念指计算机的“计算能力”不是人的“智力”。蛮力法也称穷举法或枚举法。是一种简单直接地解决问题的方法采用一定的策略依次处理待求解问题的所有元素从而找出问题的解。二时间性能用蛮力法设计的算法其时间性能往往也是最低的典型的指数时间算法一般都是通过蛮力穷举得到的。三关键——依次处理所有元素1.确定穷举范围2.保证处理过的元素不再被处理为了避免陷入重复试探四用途1.理论上蛮力法可以解决可计算领域的各种问题。2.蛮力法经常用来解决一些较小规模的问题。3.对于一些重要的问题例如排序、查找等蛮力法可以产生一些合理的算法他们具备一些实用价值而且不受问题规模的限制。4.蛮力法可作为某类问题时间性能的上界来衡量同样问题的其他算法是否具有更高的效率。二、查找问题中的蛮力法一顺序查找时间复杂度O ( n ) O(n)O(n)二串匹配问题1.问题描述给定两个串S “ s 0 s 1 … s n − 1 ” 4 S“s_0s_1…s_{n-1}” 4S“s0​s1​…sn−1​”4和T “ t 0 t 1 … t m − 1 ” T“t_0t_1…t{m-1}”T“t0​t1​…tm−1”在主串 S 中查找子串 T 的过程称为串匹配其中 T 称为模式因而这一过程也称模式匹配。2.BF算法1如何实现2时间复杂度3.KMP算法改进的模式匹配算法1BF低效原因在每趟匹配不成功时存在大量回溯没有利用已经部分匹配的结果。每趟匹配失败i要回溯到本趟匹配开始字符的下一个字符j要回溯到T的第一个字符。2设计思想主串 S 不进行回溯模式 T 要回溯到某一个字符。即让 i 不回溯尽量利用已经得到的“部分匹配”的结果信息和模式串本身所含信息让j向右“滑动”尽可能远的一段距离后加快模式串的滑动速度。三、排序问题中的蛮力法一选择排序1.基本思想第 i 趟排序从第 i 个记录开始扫描序列在n – i 1 1 ≤ i ≤ n − 1 n – i 11 ≤ i ≤ n - 1n–i11≤i≤n−1个记录中找到关键码最小的记录并和第 i 个记录交换作为有序序列的第 i 个记录。2.实例3.时间复杂度最好、最坏、平均都是O ( n 2 ) O(n^2)O(n2)二冒泡排序1.基本思想冒泡排序在扫描过程中两两比较相邻记录如果反序则交换最终最大记录就被移到了序列的最后一个位置第二遍扫描将第二大记录移到了倒数第二个位置重复上述操作直到n-1 遍扫描后整个序列就排好序了。2.时间复杂度四、图问题中的蛮力法一哈密顿回路1.问题描述2.基本思想3.时间复杂度在最坏情况下需要考察所有顶点的排列对象其时间复杂性为O ( n ! ) O(n!)O(n!)二TSP问题1.问题描述TSP问题traveling salesman problem是指旅行家要旅行n个城市然后回到出发城市要求各个城市经历且仅经历一次并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题是图问题中最广为人知的问题。2.时间复杂度蛮力法求解TSP问题必须依次考察顶点集合的所有全排列从中找出路径长度最短的简单回路因此其时间下界为Ω(n!) 。