天津科技大学算法设计与分析 第3章 蛮力法.pptVIP

算法设计与分析--蛮力法 结论: 对于一个具有n个元素的集合，其子集数量是2n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个Ω(2n)的算法。 结论 由于任务分配问题需要考虑的排列数量是n!，所以，除了该问题的一些规模非常小的实例，蛮力法几乎是不实用的。 例:蛮力法求解哈密顿回路 蛮力法求解最近对问题的过程 算法的效率 所有不同的点共组成了n(n-1)/2边，对每条边都要对其他n-2个顶点求出在直线方程ax + by = c中的符号，所以，其时间复杂性是O(n3)。 算法3.4——KMP算法中求next数组 void GetNext(char T[ ], int next[ ]) { next[1]=0; j=1; k=0; while (jT[0]) if ((k= =0)| |(T[j]= =T[k])) { j++; k++; next[j]=k; } else k=next[k]; } KMP算法用伪代码描述如下： 算法3.5——KMP算法 1. 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到next[j]位置，即j=next[j]； 2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0； KMP算法的时间复杂性是O(n+m)，当mn时，KMP算法的时间复杂性是O(n)。 3.3 排序问题中的蛮力法 3.3.1 选择排序 3.3.2 起泡排序 排序的基本概念 3.3.1 选择排序 选择排序第i趟排序从第i个记录开始扫描序列，在n-i+1（1≤i≤n-1）个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。 r1 ≤r2 … … ≤ri-1 ri ri+1 … rmin … rn 有序区 无序区 已经位于最终位置 rmin为无序区的最小记录 交换 算法3.6——选择排序 void SelectSort(int r[ ], int n) //数组下标从1开始 { for (i=1; i=n-1; i++) //对n个记录进行n-1趟简单选择排序 { index=i; for (j=i+1; j=n; j++) //在无序区中找最小记录 if (r[j]r[index]) index=j; if (index!=i) r[i]←→r[index]; //若最小记录不在最终位置则交换 } } 该算法的基本语句是内层循环体中的比较语句r[j]r[index]，其执行次数为： 起泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被“沉到”了序列的最后一个位置，第二遍扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1?遍扫描后，整个序列就排好序了。 3.3.2 起泡排序 rj rj+1 ri+1 ≤ …… ≤ rn-1 ≤rn 无序区 有序区 1≤j≤i-1 位于最终位置 反序则交换 算法3.7——起泡排序 void BubbleSort(int r[ ], int n) //数组下标从1开始 { for (i=1; i=n-1; i++) for (j=1; j=n-i; j++) if (r[j]r[j+1]) r[j]←→r[j+1]；//如果反序，则交换元素 } 该算法的基本语句是内层循环体中的比较语句r[j]r[j+1]，其执行次数为： 注意到，在一趟起泡排序过程中，如果有多个记录