《算法设计与分析》第4章穷举法

《《算法设计与分析》第4章穷举法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章穷举法4.1穷举法的设计思想4.2渐近表示法4.3算法分析2021/7/122成都学院计算机系主要知识点掌握好算法的评价标准;了解影响程序运行时间的因素;掌握算法的评价标准:时间复杂度和空间复杂度的概念;掌握渐近时间复杂度的几种表示方式;掌握常见时间复杂度渐近表示之间的关系.2021/7/123成都学院计算机系4.1穷举法思想一、穷举法定义是一种简单而直接地解决问题的方法，常常直接基于问题的描述。是最容易应用的方法，其时间性能比较低。通常典型的指数时间算法一般都是通过穷举法搜索而得到的。2

2、021/7/125成都学院计算机系二、设计思想采用的基本技术是扫描技术，即使用一定的策略将待求解问题的所有元素依次处理一次，从而找到问题的解。为了避免重复试探，在基本的数据结构中采用遍历来处理每一个元素。2021/7/126成都学院计算机系（1）集合的遍历按照元素序号的顺序依次处理每个元素。（2）线性表的遍历元素序号，如数组是按元素的下标来处理。（3）树的遍历先序、中序、后序2021/7/127成都学院计算机系三、采用穷举法的原因理论上可以解决可计算领域的各种问题。经常用来解决一些较小规模的问题

3、。对一些重要问题（排序、查找、字符串匹配等）有一些实用价值，且不受问题规模的限制。可作为某类问题时间性能下限，进行高效算法的比较。2021/7/128成都学院计算机系4.2查找问题中的穷举法顺序查找思想：从表的一端向另一端逐个将元素与给定值进行比较，若相等，查找成功，给出该元素的具体位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败！2021/7/129成都学院计算机系假设以n个数放入数组r[1]～r[n]中，查找值k的算法。intSeqsearch(intr[],intn,intk){

4、i=n;while(i>0&&r[i]!=k)i--;returni;}2021/7/1210成都学院计算机系其基本语句i>0和r[i]!=k，其执行次数缺陷：每次都要判断下标i是否越界。2021/7/1211成都学院计算机系改进方法：哨兵将k放入到r[0]中，每次将r[1]～r[n]中的值与r[0]进行比较。intSeqsearch(intr[],intn,intk){i=n;r[0]=k;while(r[i]!=k)i--;returni;}2021/7/1212成都学院计算机系其基本语句i

5、>0和r[i]!=k，其执行次数比较顺序查找方法，减少了系数。2021/7/1213成都学院计算机系4.3排序问题中的穷举法一、选择排序思想：开始扫描整个序列，找到最小记录和序列中的第一个记录交换，再从第二个记录扫描，找到最小记录与第二个记录交换，直到扫描第n-1个记录与第n个记录进行交换，使得整个序列有序。2021/7/1214成都学院计算机系一般情况，第i趟排序从第i个记录开始扫描序列，在n-i+1(1≤i≤n)个记录中找最小记录，并与第i个记录进行交换。2021/7/1215成都学院计算机

6、系VoidSelectsort(intr[],intn){for(i=1;i<=n-1;i++){index=i;for(j=i+1;j<=n;j++)//找最小记录if(r[j]r[index];}}2021/7/1216成都学院计算机系基本语句内层循环中的r[j]

7、邻记录，如反序则交换，最终将最大记录置于最后一个记录位置，第二大记录置于倒数第二个记录位置，重复至整个序列有序。2021/7/1218成都学院计算机系VoidBubblesort(intr[],intn){for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++)//找最小记录if(r[j]r[j+1];}2021/7/1219成都学院计算机系基本语句内层循环中的r[j]

8、行完。思想有没有改进的办法？有则写出算法。2021/7/1220成都学院计算机系4.5几何问题中的穷举法最近对问题要求找出一个包含n个点的集合中距离最近的两个点。应用实例：空中交通2021/7/1221成都学院计算机系前提假设1.二维空间中的点，并且点的坐标形式(x,y)给出的。2.若Pi=(xi,yi),Pj=(xj,yj)，则其间距离d:最近对问题的求解过程：分别计算每一对点之间的距离，然后找出距离最小的那一对，只考虑i