第3章 蛮力法.ppt

1、计算机与信息学院，2。使用教材，使用教材，作者：(美国)阿南尼莱维丁翻译：潘岩出版社：清华大学丛书标题：国外经典教材计算机科学与技术，第3章：蛮力方法，选择排序概述，冒泡排序，排序，排序，搜索，字符串匹配，穷举搜索，4。蛮力方法概述蛮力方法概述前面已经讨论了算法效率分析的框架和方法。本章开始讨论算法设计技术。概念：暴力法是一种简单而直接的解决问题的方法，它通常直接根据问题本身来设计算法。你可以用“动手吧！”描述蛮力策略通常是最容易想到和采用的简单而直接的算法设计策略。简单的例子：给定一个数字a和一个非负整数n，计算一个。强力方法：根据定义，设计算法是直接基于问题定义的：A和A直接相乘n次。其他

2、例子：1 .计算gcd(m，n)的连续整数检测算法：(效率不如欧几里德算法)2。使用矩阵乘法定义大型矩阵乘法的直接计算。(效率不如斯特拉赫恩算法)，5。蛮力方法概述(2)，蛮力方法的特点：1 .算法设计相对简单直接，相对容易；2.通常，算法是低效的。因此，有效的算法很少来自蛮力方法。蛮力方法的应用：它仍然是一个重要的算法设计策略。1.它可以解决广泛领域中的各种问题，几乎是解决各种问题的唯一通用方法。常用于一些非常基本和重要的算法。例如：计算n个数的和；找到列表中最大的元素，等等。2.对于一些重要的算法(如排序、搜索、矩阵乘法、字符串匹配)，蛮力方法可以产生一些合理的算法，这些算法具有一定的实用

3、价值，并且不限制问题的规模。3.对于小规模问题，当蛮力方法的计算速度可以接受时，设计有效算法的成本可能不值得。(人工成本、算法复杂性)4。蛮力方法可以服务于研究和教学，并以此为准绳来衡量其他算法对这个问题的效率。6，选择排序，选择排序排序问题：给定一个可排序的N元素序列(如数字序列和字母序列)，以非降序重新排列它们。思考问题：解决这个问题的“简单”方法是什么？选择排序算法策略：从小到大，依次找到符合要求的每个元素。1.扫描整个列表，找到最小的元素，并与第一个元素交换；2.从第二个元素开始扫描列表，在剩余的元素中找到最小的元素，并将其与第二个元素交换；3.这样做，直到所有元素都按要求排序。(求n

4、-1次)，7。选择排序效率分析，选择排序效率分析：输入规模：元素数量n；基本操作：键值比较次数。效率：该算法中键值比较的次数与输入序列顺序无关，因此没有最佳、最差或平均效率。该算法是非递归的，增长函数和增长率计算如下：结论：1 .选择排序算法的效率类型；2.密钥交换的数量是。这一特性使得选择性排序算法优于许多其他排序算法。8、选择改进的排序算法，冒泡排序的另一个应用蛮力方法在排序中，策略是比较列表中两个相邻的元素，如果它们的位置是相反的，则交换它们的位置。重复多次，最后，最大的元素将“下沉”到列表中的最后一个位置。在第二轮操作中，第二大元素被沉入，在进行了(n-1)轮之后，列表被排序。9、冒泡

5、排序效率分析，冒泡排序效率分析：输入规模：列表中元素的数量n；基本操作：键值比较次数aj1aj效率：该算法中键值比较的次数与输入序列顺序无关，因此没有最佳、最差或平均效率。该算法是非递归的，增长函数和增长率计算如下：结果：1 .气泡排序算法的效率属于类型；(与选择排序相同)2。在最坏的情况下(输入降序列表，每次比较后交换)，键值交换的数量与键值比较的数量相同，这比选择排序更糟糕。因此，该算法不是简单排序的好选择。“如果不是因为它的名字容易记住，我们可能不会知道它的任何事情。”，10，顺序搜索，顺序搜索键值“搜索”前一节讨论了蛮力方法在排序问题中的两个应用。接下来的两节讨论了这种策略在搜索问题中的两种应用，即顺序搜索和字符串匹配。搜索问题：(经典问题)如何在给定列表中找到给定值(搜索关键字)。顺序搜索的强力策略：将列表中的元素与搜索关键字逐一进行比较，直到找到匹配的元素(搜索成功)，或者遍历整个列表而没有找到匹配的元素(搜索失败)。实现顺序搜索的一个小技巧是：在列表的末尾添加搜索键，这样搜索就会成功，避免每次循环都检查列表的边界。最佳效率：Tbest(n)=1；最差效率：Tworst(n)=n1；如果给定的序列是有序的，它可以被改进