资源预览内容
第1页 / 共71页
第2页 / 共71页
第3页 / 共71页
第4页 / 共71页
第5页 / 共71页
第6页 / 共71页
第7页 / 共71页
第8页 / 共71页
第9页 / 共71页
第10页 / 共71页
亲,该文档总共71页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
算法设计与分析清华大学出版社第3章蛮力法3.1蛮力法的设计思想3.2查找问题中的蛮力法3.3排序问题中的蛮力法3.4组合问题中的蛮力法3.5图问题中的蛮力法3.6几何问题中的蛮力法3.7实验项目串匹配问题算法设计与分析清华大学出版社3.1蛮力法的设计思想蛮力法的设计思想:直接基于问题的描述。例:计算an应用举例:是RSA算法非对称加密的重要组成部分n次an=aaa算法设计与分析清华大学出版社n蛮力法所赖的基本技术扫描技术n关键依次处理所有元素(避免重复试探)n 基本的扫描技术遍历(1)集合的遍历(2)线性表的遍历(3)树的遍历 (4)图的遍历 算法设计与分析清华大学出版社 虽然巧妙和高效的算法很少来自于蛮力法,基于以下原因,蛮力法也是一种重要的算法设计技术: (1)理论上,蛮力法可以解决可计算领域的各种问题。(2)蛮力法经常用来解决一些较小规模的问题。(3)对于一些重要的问题蛮力法可以产生一些合理的算法,他们具备一些实用价值,而且不受问题规模的限制。(4)蛮力法可以作为某类问题时间性能的底限,来衡量同样问题的更高效算法。算法设计与分析清华大学出版社3.2 查找问题中的蛮力法 3.2.1顺序查找3.2.2串匹配问题算法设计与分析清华大学出版社 顺序查找从表的一端向另一端逐个将元素与给定值进行比较,若相等,则查找成功,给出该元素在表中的位置;若整个表检测完仍未找到与给定值相等的元素,则查找失败,给出失败信息。3.2.1顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向算法设计与分析清华大学出版社算法3.1顺序查找 int SeqSearch1(int r , int n, int k) /数组r1 rn存放查找集合 i=n; while (i0 & ri!=k) i-; return i; 算法3.1的基本语句是i0和ri!=k,其执行次数为:基本语句 ?算法设计与分析清华大学出版社将待查值放在查找方向的尽头处,免去了在查找过程中每一次比较后都要判断查找位置是否越界,从而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向哨兵改进的顺序查找算法设计与分析清华大学出版社算法3.2改进的顺序查找 intSeqSearch2(intr,intn,intk)/数组r1rn存放查找集合r0=k;i=n;while(ri!=k)i-;returni;算法3.2的基本语句是ri!=k,其执行次数为: 数量级相同,系数相差一半算法设计与分析清华大学出版社 用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能,但只能减少系数,而数量级不会改变。v 一般观点:算法设计与分析清华大学出版社3.2.2串匹配问题 串匹配问题属于易解问题。 串匹配问题的特征:(1)算法的一次执行时间不容忽视:问题规模 n 很大,常常需要在大量信息中进行匹配;(2)算法改进所取得的积累效益不容忽视:串匹配操作经常被调用,执行频率高。串匹配问题给定两个串S=“s1s2sn”和T=“t1t2tm”,在主串S中查找子串T的过程称为串匹配,也称模式匹配。算法设计与分析清华大学出版社 基本思想:从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;若不相等,则从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若最后一轮匹配的起始位置是n-m,则主串S中剩下的字符不足够匹配整个模式T,匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法。蛮力法解决串匹配问题BF算法算法设计与分析清华大学出版社本趟匹配开始位置si主串S模式Ttjj回溯回溯i算法设计与分析清华大学出版社设主串s=“ababcabcacbab”,模式t=“abcacababcabcacbababci=3,j=3失败;i回溯到2,j回溯到1第1趟ijijijij算法设计与分析清华大学出版社ababcabcacbabaijij第2趟i=2,j=1失败i回溯到3,j回溯到1第3趟ababcabcacbababcaci=7,j=5失败i回溯到4,j回溯到1ijijijijijji算法设计与分析清华大学出版社第4趟ababcabcacbabaiji=4,j=1失败i回溯到5,j回溯到1ji第5趟ababcabcacbabijajii=5,j=1失败i回溯到6,j回溯到1算法设计与分析清华大学出版社第6趟ababcabcacbababcaci=11,j=6,t中全部字符都比较完毕,匹配成功。ijijijijijij算法设计与分析清华大学出版社intBF(charS,charT)i=1;j=1;while(i=S0&jT0)return(i-j+1);elsereturn0;BFC+算法算法设计与分析清华大学出版社 设串S长度为n,串T长度为m,在匹配成功的情况下,考虑最坏情况,即每趟不成功的匹配都发生在串T的最后一个字符。例如:S=aaaaaaaaaaab T=aaab设匹配成功发生在si处,则在i-1趟不成功的匹配中共比较了(i-1)m次,第i趟成功的匹配共比较了m次,所以总共比较了im次,因此平均比较次数是:算法设计与分析清华大学出版社改进的串匹配算法KMP算法设计思想:尽量利用已经部分匹配的结果信息,尽量让i不回溯,加快模式串的滑动速度。算法设计与分析清华大学出版社ababcabcacbababci=3,j=3失败;第1趟iiijababcabcacbabaij第2趟s2=t2;t1t2t1s2jj算法设计与分析清华大学出版社第3趟ababcabcacbababcaci=7,j=5失败ijijijijij第4趟ababcabcacbabaijs4=t2;t1t2t1s4算法设计与分析清华大学出版社第5趟ababcabcacbabijas5=t3;t1t3t1s5第6趟ababcabcacbababcaci=11,j=6,t中全部字符都比较完毕,匹配成功。ijijijijij算法设计与分析清华大学出版社需要讨论两个问题:如何由当前部分匹配结果确定模式向右滑动的新比较起点k?模式应该向右滑多远才是最高效率的?结论:i可以不回溯,模式向右滑动到的新比较起点k ,并且k仅与模式串T有关!算法设计与分析清华大学出版社请抓住部分匹配时的两个特征:两式联立可得:T T1 1T Tk k-1-1T Tj j-( -(k k-1)-1) T Tj j-1-1S=ababcabcacbabT=abcacik(1)设模式滑动到第k个字符,则T T1 1T Tk k-1-1 S Si i-( -(k k-1)-1)Si i-1-1(2)则Tj-(k-1)Tj-1S Si i-( -(k k-1)-1) Si i-1-1jS=ababcabcacbabT=abcacikiS=ababcabcacbabT=abcacjk算法设计与分析清华大学出版社T T1 1TTk k-1-1T Tj j-( -(k k-1)-1)TTj j-1-1说明了什么?说明了什么?(1)k与 j具有函数关系,由当前失配位置j ,可以计算出滑动位置k(即比较的新起点);(2)滑动位置k仅与模式串T有关。从第1位往右经过k-1位从j-1位往左经过k-1位kmaxk|1kj且T1Tk-1Tj-(k-1)Tj-1T T1 1TTk k-1-1T Tj j-( -(k k-1)-1)TTj j-1-1的物理意义是什么?的物理意义是什么?模式应该向右滑多远才是最高效率的?算法设计与分析清华大学出版社nextj0当j1时/不比较maxk|1kj且T1Tk-1=Tj-(k-1)Tj-11其他情况令k=nextj,则:t1t2t3t4t5t6a b a b a c真前缀真后缀t1=t5, t1t2t3=t3t4t5a和aba都是ababa的真前缀和真后缀,但aba的长度最大next6=3+1=4即当t6和si匹配失败后,将t4和si进行比较nextj函数表征着模式T中最大相同首子串和尾子串(真子串)的长度。可见,模式中相似部分越多,则nextj函数越大,模式串向右滑动得越远,与主串进行比较的次数越少,时间复杂度就越低。算法设计与分析清华大学出版社此时,比较tk和tj,可能出现两种情况:(1)tktj:说明t1tk-1tktj-k+1tj-1tj,由前缀函数定义,nextj+1=k1;由模式T的前缀函数定义易知,next1=0,假设已经计算出next1,next2,nextj,如何计算nextj1呢?设k=nextj,这意味着t1tk-1既是t1tj-1的真后缀又是t1tj-1的真前缀,即: t1tk-1tj-k+1tj-k+2tj-1计算nextj的方法:算法设计与分析清华大学出版社t1tnextk-1tnextktk-1tktj-nextk+1tj-1tjtj+1t1tnextk-1tnextktk-1tktj-nextk+1tj-1tjtj+1最大真前缀最大真后缀最2大真前缀最2大真后缀(2)tktj:此时要找出t1 tj-1的后缀中第2大真前缀,显然,这个第2大的真前缀就是nextnextj=nextk。算法设计与分析清华大学出版社再比较tnextk和tj,此时仍会出现两种情况,当tnextktj时,与情况(1)类似,nextj+1=nextk+1;当tnextktj时,与情况(2)类似,再找t1tj-1的后缀中第3大真前缀,重复(2)的过程,直到找到t1tj-1的后缀中的最大真前缀,或确定t1tj-1的后缀中不存在真前缀,此时,nextj+1=1。t1tnextk-1tnextktk-1tktj-nextk+1tj-1tjtj+1最2大真前缀最2大真后缀算法设计与分析清华大学出版社j=6时,t2t5,next6=3;j=7时,t3t6,next7=4;j=8时,t4t7,k=next4=2,t2t7,next8=k+1=3。例如,模式T=a b a a b a b c的next值计算如下:j=1时,next1=0;j=2时,next2=1;j=3时,t1t2,next3=1;j=4时,t1t3,next4=2;j=5时,t2t4,令k=next2=1,t1t4,next5=k+1=2;算法设计与分析清华大学出版社算法3.4KMP算法中求next数组void GetNext(char T , int next ) next1=0; j=1; k=0; while (jT0) if (k= =0)| |(Tj= =Tk) j+; k+; nextj=k; else k=nextk;算法设计与分析清华大学出版社KMP算法用伪代码描述如下: 算法3.5KMP算法 1. 在串S和串T中分别设比较的起始下标i和j; 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果Si=Tj,则继续比较S和T的下一个字符;否则 2.2 将j向右滑动到nextj位置,即j=nextj; 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(1in-1)个记录中找到关键码最小的记录,并和第i个记录交换作为有序序列的第i个记录。 r1r2ri-1 ri ri+1rmin rn 有序区无序区已经位于最终位置rmin为无序区的最小记录交换算法设计与分析清华大学出版社算法3.6选择排序voidSelectSort(intr,intn) /数组下标从1开始for(i
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号