算法设计与分析基础第2版清华出版社算法分析第3章

《算法设计与分析基础第2版清华出版社算法分析第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章蛮力法蛮力法一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。虽然巧妙和高效的算法很少来自于蛮力法，但我们不应该忽略它作为一种重要的算法设计策略的地位。第一，和其他某些策略不同，我们可以应用蛮力法来解决广阔领域的各种问题。第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法，它们多少具备上些实用价值，而且并不限制实例的规模。第三，如果要解决的问题实例不多，而且蛮力法可以用一种能够接受速度对实例求解，那么，设计一个更高效算法所花费的代价很可能是不值

2、得的。第四，即使效率通常很低，仍然可以用蛮力法解决一些小规模的问题实例。最后，一个蛮力算法可以为研究或教学目的的服务。3.1选择排序和冒泡排序算法SelectionSort(A[0..n-1])//该算法用选择排序对给定的数组排序//输入：一个可排序数组A[0..n-1]//输出：非降序排序的数组A[0..n-1]fori←0ton-2domin←Iforj←i+1ton-1doifA[j]<[min]min←jswapA[i]andA[min]A0≤A1≤…Ai-1

3、Ai,…,Amin,…,An-1已经位于最终的位置上

4、了最后的n-1个元素3.1.1选择排序

5、8945689029341717

6、4568902934891729

7、6890453489172934

8、9045688917293445

9、9068891729344568

10、9089172934456889

11、90选择排序对于序列89，45，68，90，29，34，17，所做的操作3.1.2冒泡排序A0,…,Aj↔Aj+1,…,An-i-1

12、An-i≤…≤An-1?已经位于最终的位置上了算法BubbleSort(A[0..n-1])//该算法用冒泡排序对数组A[0..n-1]排序//输入

13、：一个可排序数组A[0..n-1]//输出：非降序排列的数组A[0..n-1]fori←0ton-2doforj←0ton-2-idoifA[j+1]

14、,29,34,17的前两遍操作。每次交换了两个元素的位置以后，就另起一行。竖线右面的元素已经位于它们的最终位置，所以在后面的循环中就不再考虑了。对于所有规模为n的数组来说,该冒泡排序版本的键值比较次数都是相同的,我们可以用下面这个求和表达式来表示。它和选择排序的表达式几乎是完全相同的：但它的键交换次数取决于特定的输入。最坏的情况下就是遇到降序的数组，这是，键交换次数和键比较次数是相同的：3.2.1顺序查找该算法只是简单地将给定列表中的连续元素和给定的查找键作比较，直到遇到一个匹配的元素（查找成功），或者在遇到元素前就遍历

15、了整个列表（失败查找）算法SequentialSearch2(A[0..n],K)//顺序查找的算法实现，它用了查找键来做限位器//输入：一个n个元素的数组A和一个查找键K//输出：第一个值等于K的元素的位置，如果找不到这样的元素，返回-13.2顺序查找和蛮力字符串匹配A[n]←Ki←0whileA[i]≠Kdoi←i+1ifi

16、符串匹配问题：给定一个子n个字符组成的串，称为文本，一个m个字符的串，称为模式，从文本中寻找匹配模式的子串。更精确地说，我们求的是i——文本中的第一个匹配子串最左元素的下标——使得ti=p0,…,ti+j=pj,…,ti+m-1=pm-1:t0…ti…ti+j…ti+m-1…tn-1textTP0…Pj…Pm-1patternP算法BruteForceStringMatch(T[0..n-1],P[0..m-1])//该算法实现了蛮力字符串匹配//输入：一个n个字符的数组T[0..n-1]代表一段文本//一个m个字符的数

17、组P[0..n-1]代表一个模式//输出：如果查找成功的话，返回文本的第一个匹配子串//中第一个字符的位置//否则返回-1fori←0ton-mdoj←0whilej