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

第4章穷举法2023/6/51成都学院计算机系4.1穷举法的设计思想4.2渐近表示法

4.3算法分析2023/6/52成都学院计算机系主要知识点掌握好算法的评价标准;了解影响程序运行时间的因素;掌握算法的评价标准:时间复杂度和空间复杂度的概念;掌握渐近时间复杂度的几种表示方式;掌握常见时间复杂度渐近表示之间的关系.2023/6/53成都学院计算机系4.1穷举法思想2023/6/54成都学院计算机系一、穷举法定义是一种简单而直接地解决问题的方法，常常直接基于问题的描述。是最容易应用的方法，其时间性能比较低。通常典型的指数时间算法一般都是通过穷举法搜索而得到的。2023/6/55成都学院计算机系二、设计思想采用的基本技术是扫描技术，即使用一定的策略将待求解问题的所有元素依次处理一次，从而找到问题的解。为了避免重复试探，在基本的数据结构中采用遍历来处理每一个元素。2023/6/56成都学院计算机系（1）集合的遍历按照元素序号的顺序依次处理每个元素。（2）线性表的遍历元素序号，如数组是按元素的下标来处理。（3）树的遍历先序、中序、后序2023/6/57成都学院计算机系三、采用穷举法的原因理论上可以解决可计算领域的各种问题。经常用来解决一些较小规模的问题。对一些重要问题（排序、查找、字符串匹配等）有一些实用价值，且不受问题规模的限制。可作为某类问题时间性能下限，进行高效算法的比较。2023/6/58成都学院计算机系4.2查找问题中的穷举法顺序查找思想：从表的一端向另一端逐个将元素与给定值进行比较，若相等，查找成功，给出该元素的具体位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败！2023/6/59成都学院计算机系假设以n个数放入数组r[1]～r[n]中，查找值k的算法。

int

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

Seqsearch(intr[],intn,intk){i=n;r[0]=k;while(r[i]!=k)i--;returni;}2023/6/512成都学院计算机系其基本语句i>0和r[i]!=k，其执行次数比较顺序查找方法，减少了系数。2023/6/513成都学院计算机系4.3排序问题中的穷举法一、选择排序思想：开始扫描整个序列，找到最小记录和序列中的第一个记录交换，再从第二个记录扫描，找到最小记录与第二个记录交换，直到扫描第n-1个记录与第n个记录进行交换，使得整个序列有序。2023/6/514成都学院计算机系一般情况，第i趟排序从第i个记录开始扫描序列，在n-i+1(1≤i≤n)个记录中找最小记录，并与第i个记录进行交换。2023/6/515成都学院计算机系VoidSelectsort(int

r[],intn){for(i=1;i<=n-1;i++){index=i;for(j=i+1;j<=n;j++)//找最小记录if(r[j]<r[index])index=j;if(index!=i)r[j]>r[index];}}2023/6/516成都学院计算机系基本语句内层循环中的r[j]<r[index]，其执行次数为：选择排序最多交换n-1次数据。

2023/6/517成都学院计算机系二、冒泡排序一开始就扫描整个序列，在扫描的过程中两两比较相邻记录，如反序则交换，最终将最大记录置于最后一个记录位置，第二大记录置于倒数第二个记录位置，重复至整个序列有序。2023/6/518成都学院计算机系VoidBubblesort(int

r[],intn){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];}

2023/6/519成都学院计算机系基本语句内层循环中的r[j]<r[j+1]，其执行次数为：不足：如果整个序列已经有序，还是要直接整个外循环执行完。思想有没有改进的办法？有则写出算法。2023/6/520成都学院计算机系4.5

几何问题中的穷举法最近对问题要求找出一个包含n个点的集合中距离最近的两个点。应用实例：空中交通2023/6/521成都学院计算机系前提假设

1.二维空间中的点，并且点的坐标形式(x,y)给出的。

2.若Pi=(xi,yi),Pj=(xj,yj)，则其间距离d:

最近对问题的求解过程：分别计算每一对点之间的距离，然后找出距离最小的那一对，只考虑i<j的那些点对。

2023/6/522成都学院计算机系int

closetpoint(int

n,int

x[],int

y[],int&index1,int&index2){mindist=+∞;for(i=1;i<n;i++)for(j=i+1;j<=n;j++){d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);if(d<mindist){mindist=d;index1=i;index2=j;}}returnmindist;}2023/6/523成都学院计算机系实验—串匹配题目：给定一个文本，在该文本中查找并定位任意给定字符串实验目的：理解并掌握穷举法的设计思想；实验要求：

1.实现BF算法及对其的改进算法BM算法

2.对BF、BM进行时间复杂度的分析并编程验证。2023/6/524成都学院计算机系BM算法基本思想：假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中，若发现不匹配，则下次应从主串的i+dist(si)位置开始重新进行新一轮的匹配，其效果相当于把模式和主串均右滑过一段距离dist(si),即跳过dist(si)个字符而无需进行比较。2023/6/525成都学院计算机系假设字符表{a,b,c,……,z}，BM算法对给定的模式T=“t1t2…tm”,定义一个从字符到正整数的映射：

dist:c{1,2,…，m},c属于字符表滑动函数给出了正文中可能出现的任意字符在模式中的位置，定义如下：

m-jj=max{j|tj=c且1≤j≤m-1

dist(c)=c若c不出现在模式中或tm=c2023/6/526成都学院计算机系Int

BM(char

s[],char

t[],int

n,intm){i=m;//模式串长度

while(i<=n){j