第3章-蛮力法资料课件.ppt

《第3章-蛮力法资料课件.ppt》由会员分享，可在线阅读，更多相关《第3章-蛮力法资料课件.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2023/1/1算法设计与分析-蛮力法1第第3章章蛮力法蛮力法3.1概述概述3.2查找问题中的蛮力法查找问题中的蛮力法3.3排序问题中的蛮力法排序问题中的蛮力法3.4组合问题中的蛮力法组合问题中的蛮力法3.5图问题中的蛮力法图问题中的蛮力法3.6几何问题中的蛮力法几何问题中的蛮力法2023/1/1算法设计与分析-蛮力法23.1概述概述蛮力法蛮力法(穷举法穷举法)，是一种简单而直接地解决问题的方，是一种简单而直接地解决问题的方法。设计思想：直接基于问题的描述。法。设计思想：直接基于问题的描述。n次an=aaa例：计算例：计算an3.1.1蛮力法的设计思想蛮力法的设计思想2023/1/1算法设计与

2、分析-蛮力法3应用实例应用实例:计算计算an的值是的值是RSA算法的主要组成算法的主要组成部分。部分。RSA算法的加密和解密过程都需要一算法的加密和解密过程都需要一个整数的整数次幂再取模。个整数的整数次幂再取模。n例如，设公钥为例如，设公钥为(5,119)，私钥为，私钥为(77,119)，明，明文文m=19，则加密得密文，则加密得密文c为：为：nc=195 mod 119=2 476 099 mod 119=66n解密得明文解密得明文m为：为：nm=6677 mod 119=19n计算计算an算法的效率直接影响到算法的效率直接影响到RSA算法的性能。算法的性能。2023/1/1算法设计与分析-

3、蛮力法4n蛮力法所依赖的基本技术蛮力法所依赖的基本技术扫描技术扫描技术n关键关键依次处理所有元素依次处理所有元素 n基本的扫描技术基本的扫描技术遍历遍历（1）集合的遍历）集合的遍历（2）线性表的遍历）线性表的遍历（3）树的遍历）树的遍历（4）图的遍历）图的遍历 2023/1/1算法设计与分析-蛮力法5蛮力法也是一种重要的算法设计技术，原因如下：蛮力法也是一种重要的算法设计技术，原因如下：（1）理理论论上上，蛮蛮力力法法可可以以解解决决可可计计算算领领域域的的各各种问题。种问题。（2）蛮力法经常用来解决一些较小规模的问题。）蛮力法经常用来解决一些较小规模的问题。（3）对对于于一一些些重重要要的的

4、问问题题（如如：排排序序、查查找找）蛮力法可以产生一些合理的算法。蛮力法可以产生一些合理的算法。（4）蛮力法可以作为某类问题时间性能的底限）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。，来衡量同样问题的更高效算法。2023/1/1算法设计与分析-蛮力法6举例：百元买百鸡问题举例：百元买百鸡问题已已知知公公鸡鸡5元元一一只只，母母鸡鸡3元元一一只只，小小鸡鸡1元元三三只只，用用100元元钱钱买买100只只鸡鸡，问问公公鸡鸡、母鸡、小鸡各多少只？母鸡、小鸡各多少只？2023/1/1算法设计与分析-蛮力法73.2 查找问题中的蛮力法查找问题中的蛮力法 3.2.1顺序查找顺序查找

5、3.2.2串匹配问题串匹配问题2023/1/1算法设计与分析-蛮力法8 顺序查找从表的一端向另一端顺序查找从表的一端向另一端逐个逐个将元素与给将元素与给定值进行比较，若相等，则查找成功，给出该元素定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。相等的元素，则查找失败，给出失败信息。3.2.1顺序查找顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向2023/1/1算法设计与分析-蛮力法9算法算法3.1顺序查

6、找顺序查找 int SeqSearch1(int r,int n,int k)/数组r1 rn存放查找集合 i=n;while(i0&ri!=k)i-;return i;算法算法3.1的的基本语句基本语句是是i0和和ri!=k，其执行次数为，其执行次数为:基本语句基本语句？其其中中pi是是第第i个个元元素素的的查查找找概概率率，而而bi和和ci分分别别是是基基本本语语句句i0和和ri!=k的执行次数的执行次数2023/1/1算法设计与分析-蛮力法10将将待查值待查值放在查找方向的放在查找方向的尽头尽头处，免去了在查找过处，免去了在查找过程中每一次比较后都要判断查找位置是否程中每一次比较后都要判

7、断查找位置是否越界越界，从，从而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向哨兵哨兵改进的顺序查找改进的顺序查找2023/1/1算法设计与分析-蛮力法11算法3.2改进的顺序查找 intSeqSearch2(intr,intn,intk)/数组数组r1rn存放查找集合存放查找集合r0=k;i=n;while(ri!=k)i-;returni;算法算法3.2的的基本语句基本语句是是ri!=k，其执行次数为，其执行次数为:数量级相同，数量级相同，系数相差一半系数相差一半2023/1/1算法设计与分

8、析-蛮力法12 用蛮力法设计的算法，都可以对算法的第用蛮力法设计的算法，都可以对算法的第一个版本进行一定程度的改良，改进其时间一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。性能，但只能减少系数，而数量级不会改变。v 一般观点：一般观点：2023/1/1算法设计与分析-蛮力法133.2.2串匹配问题串匹配问题（略）（略）串匹配问题属于易解问题。串匹配问题属于易解问题。串匹配问题的特征：串匹配问题的特征：（1）算法的一次执行时间不容忽视：问题规模）算法的一次执行时间不容忽视：问题规模 n 很大，很大，常常需要在大量信息中进行匹配；常常需要在大量信息中进行匹配；（2）

9、算法改进所取得的积累效益不容忽视：串匹配操作）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。经常被调用，执行频率高。串匹配问题串匹配问题给定两个串给定两个串S=“s1s2sn”和和T=“t1t2tm”，在，在主串主串S中查找子串中查找子串T的过程称为的过程称为串匹配串匹配，也称模式匹配。，也称模式匹配。2023/1/1算法设计与分析-蛮力法143.3排序问题中的蛮力法排序问题中的蛮力法3.3.1选择排序选择排序3.3.2起泡排序起泡排序排序：给定一个记录序列排序：给定一个记录序列(r(r1 1,r,r2 2,r,rn n)，其相应的，其相应的关键字分别为关键字分别为(k(

10、k1 1,k,k2 2,k,kn n)，排序是将这些记录，排序是将这些记录排列成顺序为排列成顺序为(r(rs1s1,r,rs2s2,r,rsnsn)的一个序列，使得相的一个序列，使得相应的关键字满足应的关键字满足k ks1s1 k ks2 s2 k ksnsn(升序或非降序升序或非降序)或或 k ks1s1 k ks2 s2 k ksn sn(降序或非升序降序或非升序)。2023/1/1算法设计与分析-蛮力法153.3.1选择排序选择排序选选择择排排序序第第i趟趟排排序序从从第第i个个记记录录开开始始扫扫描描序序列列，在在n-i+1（1in-1）个个记记录录中中找找到到关关键键码码最最小小的的

11、记记录，并和第录，并和第i个记录交换作为有序序列的第个记录交换作为有序序列的第i个记录。个记录。r1r2ri-1 ri ri+1rmin rn 有序区有序区无序区无序区已经位于最终位置已经位于最终位置rmin为无序区的最小记录为无序区的最小记录交换交换2023/1/1算法设计与分析-蛮力法16算法算法3.6选择排序选择排序voidSelectSort(intr,intn)/数组下标从数组下标从1 1开始开始for(i=1;i=n-1;i+)/对对n个记录进行个记录进行n-1趟简单选择排序趟简单选择排序index=i;for(j=i+1;j=n;j+)/在无序区中找最小记录在无序区中找最小记录i

12、f(rjrindex)index=j;if(index!=i)ririndex;/若最小记录不在最终位置则交换若最小记录不在最终位置则交换 该算法的基本语句是内层循环体中的比较语句该算法的基本语句是内层循环体中的比较语句rjrindex，其执行次数为：，其执行次数为：2023/1/1算法设计与分析-蛮力法17起泡排序在扫描过程中两两比较相邻记录，如果反起泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被序则交换，最终，最大记录就被“沉到沉到”了序列的了序列的最后一个位置，第二遍扫描将第二大记录最后一个位置，第二遍扫描将第二大记录“沉到沉到”了倒数第二个位置，重复上述操作，直

13、到了倒数第二个位置，重复上述操作，直到n-1遍扫遍扫描后，整个序列就排好序了。描后，整个序列就排好序了。解释冒泡的含义解释冒泡的含义3.3.2起泡排序起泡排序rjrj+1 ri+1 rn-1rn无序区无序区有序区有序区1ji-1位于最终位置位于最终位置反序则交换反序则交换2023/1/1算法设计与分析-蛮力法18算法算法3.7起泡排序起泡排序voidBubbleSort(intr,intn)/数组下标从数组下标从1 1开始开始for(i=1;i=n-1;i+)for(j=1;jrj+1)rjrj+1；/如果反序，则交换元素如果反序，则交换元素 该算法的基本语句是内层循环体中的比较语该算法的基本

14、语句是内层循环体中的比较语句句rjrj+1，其执行次数为：，其执行次数为：2023/1/1算法设计与分析-蛮力法19基于起泡排序的特点，可对上述算法进行改进：基于起泡排序的特点，可对上述算法进行改进：算法算法3.8改进的起泡排序改进的起泡排序voidBubbleSort(intr,intn)/数组下标从数组下标从1 1开始开始exchange=n;/第一趟起泡排序的范围是第一趟起泡排序的范围是r1到到rnwhile(exchange)/仅当上一趟排序有记录交换才进行本趟排序仅当上一趟排序有记录交换才进行本趟排序bound=exchange;exchange=0；for(j=1;jrj+1)rj

15、rj+1；exchange=j；/记录每一次发生记录交换的位置记录每一次发生记录交换的位置2023/1/1算法设计与分析-蛮力法20在在最好情况最好情况下，待排序记录序列为正序，算下，待排序记录序列为正序，算法只执行一趟，进行了法只执行一趟，进行了n-1次关键码的比较，次关键码的比较，不需要移动记录，时间复杂性为不需要移动记录，时间复杂性为O(n)例：正序例：正序 1 2 3 4 5 6 7 8 9 10例：反序例：反序 10 9 8 7 6 5 4 3 2 12023/1/1算法设计与分析-蛮力法21最坏情况：最坏情况：记录的比较次数为记录的比较次数为 关键码的移动次数为关键码的移动次数为因

16、此，时间复杂性为因此，时间复杂性为O(n2)；平均情况：平均情况：时间复杂性与最坏情况同数量级。时间复杂性与最坏情况同数量级。2023/1/1算法设计与分析-蛮力法223.4 3.4 组合问题中的蛮力法组合问题中的蛮力法 3.4.10/1背包问题背包问题3.4.2任务分配问题任务分配问题补充补充生成排列对象生成排列对象3.4.4要求生成并依次考察问题域中的每一个要求生成并依次考察问题域中的每一个元素，从中选出满足问题的约束的元素。元素，从中选出满足问题的约束的元素。易产生组合爆炸现象。易产生组合爆炸现象。2023/1/1算法设计与分析-蛮力法233.4.10/1背包问题背包问题0/1背背包包问

17、问题题是是给给定定n个个重重量量为为w1,w2,wn、价价值值为为v1,v2,vn的的物物品品和和一一个个容容量量为为C的的背背包包，求求这这些些物物品品中中的的一一个个最最有有价价值值的的子子集集，并并且且要要能能够够装到背包中。装到背包中。用蛮力法解决用蛮力法解决0/1背包问题，需要考虑给定背包问题，需要考虑给定n个物个物品集合的所有子集，找出所有可能的子集（总重量品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。然后在他们中找到价值最大的子集。2023/1/1算法设计与分

18、析-蛮力法2410w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包背包物品物品1物品物品2物品物品3物品物品481,412161,2,3,419序号序号子集子集总重量总重量总价值总价值序号序号子集子集总重量总重量总价值总价值10092,375221742102,483732312113,496543440121,2,314不可行不可行54525131,2,41561,21054141,3,41671,311不可行不可行152,3,412不可行不可行不可行不可行不可行不可行不可行不可行不可行不可行2023/1/1算法设计与分析-蛮力法25结论结论:对对于一个具有于一个

19、具有n个元素的集合，其子集个元素的集合，其子集数量是数量是2n，所以，不，所以，不论论生成子集的算法效率生成子集的算法效率有多高，蛮力法都会有多高，蛮力法都会导导致一个致一个(2n)的算法。的算法。2023/1/1算法设计与分析-蛮力法263.4.2任务分配问题任务分配问题 假设有假设有n个任务需要分配给个任务需要分配给n个人执行，每个人执行，每个任务只分配给一个人，每个人只分配一个任个任务只分配给一个人，每个人只分配一个任务，且第务，且第j个任务分配给第个任务分配给第i个人的成本是个人的成本是Ci,j（1i,jn），任务分配问题要求找出总成本），任务分配问题要求找出总成本最小的分配方案。最小

20、的分配方案。2023/1/1算法设计与分析-蛮力法27 下面是一个任务分配问题的成本矩阵，矩阵元下面是一个任务分配问题的成本矩阵，矩阵元素素Ci,j代表将任务代表将任务j分配给人员分配给人员i的成本。的成本。C=927643581任务任务1任务任务2任务任务3人员人员1人员人员2人员人员3 任务分配问题任务分配问题就是在分配成本矩阵中的每一行就是在分配成本矩阵中的每一行选取一个元素，这些元素分别属于不同的列，并且选取一个元素，这些元素分别属于不同的列，并且元素之和最小。元素之和最小。2023/1/1算法设计与分析-蛮力法28 用一个用一个n元组元组(j1,j2,jn)来描述任务分配问题的来描述

21、任务分配问题的一个可能解，其中第一个可能解，其中第i个分量个分量ji（1in）表示在第）表示在第i行行中选择的列号，因此用蛮力法解决任务分配问题要中选择的列号，因此用蛮力法解决任务分配问题要求生成整数求生成整数1n的全排列，然后把成本矩阵中的相应的全排列，然后把成本矩阵中的相应元素相加来求得每种分配方案的总成本，最后选出元素相加来求得每种分配方案的总成本，最后选出具有最小和的方案。具有最小和的方案。序号序号分配方案分配方案总成本总成本11,2,39+4+1=1421,3,29+3+8=2032,1,32+6+1=942,3,12+3+5=1053,1,27+6+8=2163,2,17+4+5=

22、162023/1/1算法设计与分析-蛮力法29结论 由于任务分配问题需要考虑的排列数量是由于任务分配问题需要考虑的排列数量是n!，所以，除了该问题的一些规模非常小的实例，所以，除了该问题的一些规模非常小的实例，蛮力法几乎是不实用的。蛮力法几乎是不实用的。2023/1/1算法设计与分析-蛮力法30补充：补充：生成排列对象生成排列对象假设已经生成了所有假设已经生成了所有(n-1)!个排列，可以把个排列，可以把n插入到插入到n-1个元素的每一种排列中的个元素的每一种排列中的n个位置中去，来得到个位置中去，来得到问题规模为问题规模为n的所有排列。按照这种方式生成的所的所有排列。按照这种方式生成的所有排

23、列都是独一无二的，并且他们的总数应该是有排列都是独一无二的，并且他们的总数应该是n(n-1)!=n!。开始开始1插入插入21221插入插入3123132312213231321生成排列的过程生成排列的过程2023/1/1算法设计与分析-蛮力法31算法算法3.9生成排列对象生成排列对象1生成初始排列生成初始排列1；2for(i=2;i=n;i+)for(j=1;j=1;k-)将将i插入到第插入到第j个排列中的第个排列中的第k个位置；个位置；显然，算法显然，算法3.9的时间复杂性为的时间复杂性为O(n!)，也就，也就是说和排列对象的数量成正比。是说和排列对象的数量成正比。2023/1/1算法设计与

24、分析-蛮力法32补充：补充：生成子集生成子集 n个个元元素素的的集集合合A=a1,a2,an的的所所有有2n个个子子集和长度为集和长度为n的所有的所有2n个比特串之间的一一对应关系。个比特串之间的一一对应关系。建建立立对对应应关关系系：为为每每一一个个子子集集指指定定一一个个比比特特串串b1b2bn，如如果果ai属属于于该该子子集集，则则bi1；如如果果ai不不属属于该子集，则于该子集，则bi0（1in）。）。比特串比特串000001010011100101110111子集子集a3a2a2,a3a1a1,a3a1,a2a1,a2,a22023/1/1算法设计与分析-蛮力法33生成生成n个元素子

25、集的算法如下：个元素子集的算法如下：算法算法3.10生成子集生成子集1初始化一个长度为初始化一个长度为n的比特串的比特串s=000并将对应的子集输出；并将对应的子集输出；2for(i=1;i2n;i+)2.1s+；2.2将将s对应的子集输出；对应的子集输出；显然，算法显然，算法3.10的时间复杂性为的时间复杂性为O(2n)，也就，也就是说和子集的数量成正比。是说和子集的数量成正比。2023/1/1算法设计与分析-蛮力法343.5图问题中的蛮力法图问题中的蛮力法3.5.1哈密顿回路问题哈密顿回路问题3.5.2TSP问题问题2023/1/1算法设计与分析-蛮力法353.5.1哈密顿回路问题哈密顿回

26、路问题 著著名名的的爱爱尔尔兰兰数数学学家家哈哈密密顿顿（WilliamHamilton，18051865）提提出出了了著著名名的的周周游游世世界界问问题题。他他用用正正十十二二面面体体的的20个个顶顶点点代代表表20个个城城市市，要要求求从从一一个个城城市市出出发发，经过每个城市恰好一次，然后回到出发城市。经过每个城市恰好一次，然后回到出发城市。1983141202131545679101112161718正十二面体的展开图，正十二面体的展开图，按照图中的顶点编号所按照图中的顶点编号所构成的回路，就是哈密构成的回路，就是哈密顿回路的一个解。顿回路的一个解。2023/1/1算法设计与分析-蛮力

27、法36使使用用蛮蛮力力法法寻寻找找哈哈密密顿顿回回路路的的基基本本思思想想是是：对对于于给给定定的的无无向向图图G=(V,E)，首首先先生生成成图图中中所所有有顶顶点点的的排排列列对对象象(vi1,vi2,vin)，然然后后依依次次考考察察每每个个排排列列对对象象是否满足以下两个条件：是否满足以下两个条件：（1）相邻顶点之间存在边，即）相邻顶点之间存在边，即(vij,vij+1)E（1jn-1）（2）最后一个顶点和第一个顶点之间存在边，即）最后一个顶点和第一个顶点之间存在边，即(vin,vi1)E 满足这两个条件的回路就是哈密顿回路。满足这两个条件的回路就是哈密顿回路。目前没有有效的算法求解哈

28、密顿回路问题目前没有有效的算法求解哈密顿回路问题2023/1/1算法设计与分析-蛮力法3712453路径路径(vij,vij+1)E1234512345（是）（是）1235412354（否）（否）1243512435（否）（否）否否否否1245312453（否）（否）1253412534（否）（否）1254312543（是）（是）(vin,vi1)E是是是是是是是是(a)一个无向图一个无向图 显然，蛮力法求解哈密顿回路在最坏情况下需要考察显然，蛮力法求解哈密顿回路在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为所有顶点的排列对象，其时间复杂性为O(n!)。例:蛮力法求解哈密顿回路(b)哈

29、密顿回路求解过程哈密顿回路求解过程2023/1/1算法设计与分析-蛮力法383.5.2TSP问题问题 TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市然后回到个城市然后回到出发城市，要求各个城市经历且仅经历一次，并出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人邮递员问题、售货员问题，是图问题中最广为人知的问题。知的问题。用蛮力法解决用蛮力法解决TSPTSP问题，可以找出所有可能问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。的旅行路线，从中选取路

30、径长度最短的简单回路。2023/1/1算法设计与分析-蛮力法398abdc23571序号序号路径路径路径长度路径长度是否最短是否最短1abcda18 否否2abdca11 是是3acbda23 否否4acdba11 是是5adbca23 否否6adcba18 否否 若若有有n n个个城城市市，则则可可能能的的解解有有(n-1)!/2个个。随随着着n的增长，的增长，TSP问题的可能解也在迅速地增长。问题的可能解也在迅速地增长。2023/1/1算法设计与分析-蛮力法40l一个一个10城市的城市的TSP问题有大约有问题有大约有180,000个可能解。个可能解。l一个一个20城市的城市的TSP问题有大

31、约有问题有大约有60,000,000,000,000,000个可能解。个可能解。l一个一个50城市的城市的TSP问题有大约问题有大约1062个可能解，而一个个可能解，而一个行星上也只有行星上也只有1021升水。升水。例如：例如：u用蛮力法求解用蛮力法求解TSP问题，只能解决问题问题，只能解决问题规模很小的实例。规模很小的实例。2023/1/1算法设计与分析-蛮力法413.6几何问题中的蛮力法几何问题中的蛮力法3.6.1最近对问题最近对问题3.6.2 凸包问题凸包问题2023/1/1算法设计与分析-蛮力法423.6.1最近对问题最近对问题最近对问题要求找出一个包含最近对问题要求找出一个包含n个点

32、的集合中个点的集合中距离最近的两个点。距离最近的两个点。考虑二维情况，并假设两个点考虑二维情况，并假设两个点Pi=(xi,yi)和和Pj=(xj,yj)之间的距离是标准的欧几里德距离：之间的距离是标准的欧几里德距离：2023/1/1算法设计与分析-蛮力法43分别计算每一对点之间的距离，然后找分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑对点计算两次距离，只考虑ij的那些的那些点对点对(Pi,Pj)。蛮力法求解最近对问题的过程蛮力法求解最近对问题的过程2023/1/1算法设计与分析-蛮力法44算法算法3.11最近对问

33、题最近对问题intClosestPoints(intn,intx,inty,int&index1,int&index2)minDist=+;for(i=1;in;i+)for(j=i+1;j=n;j+)d=(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);if(d2个点（不共线）的集合个点（不共线）的集合S的凸包是以的凸包是以S中的某些点为顶点的凸多边形；如中的某些点为顶点的凸多边形；如果所有点都位于一条直线上，则凸多边形退化为果所有点都位于一条直线上，则凸多边形退化为一条线段。一条线段。2023/1/1算法设计与分析-蛮力法49 蛮力法求解凸包问题的基本思想：对于一蛮力法求解凸

34、包问题的基本思想：对于一个由个由n个点构成的集合个点构成的集合S中的两个点中的两个点Pi和和Pj，当，当且当该集合中的其他点都位于穿过这两点的直且当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况）线的同一边时（假定不存在三点同线的情况），他们的连线是该集合凸包边界的一部分。对，他们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。成了该凸包的边界。2023/1/1算法设计与分析-蛮力法50这这样样一一条条直直线线把把平平面面分分成成两两个个半半平平面面：其其中中一一个个半半平平面面中中

35、的的点点都都满满足足ax+byc，另另一一个个半半平平面面中中的的点点都都满满足足ax+byc，因因此此，为为了了检检验验这这些些点点是是否否位位于于这这条条直直线线的的同同一一边边，可可以以简简单单地地把把每每个个点点代代入入表表达达式式ax+by-c，检检验验这这些些表表达达式式的的符符号号是是否否相相同。同。在平面上，过两个点在平面上，过两个点(x1,y1)和和(x2,y2)的直线是由下面的直线是由下面的方程定义的：的方程定义的：ax+by=c(其中，其中，a=y2-y1,b=x1-x2,c=x1y2-y1x2)2023/1/1算法设计与分析-蛮力法51算法的效率算法的效率所所有有不不同同的的点点共共组组成成了了n(n-1)/2边边，对对每每条条边边都都要要对对其其他他n-2个个顶顶点点求求出出表表达达式式ax+by-c的符号，所以，其时间复杂性是的符号，所以，其时间复杂性是O(n3)。