算法分析与设计-复习提纲ppt课件.ppt

《算法分析与设计-复习提纲ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计常熟理工学院计算机学院刘在德第1章绪论掌握三种渐近符号（O、Ω、Θ）的含义；会用三种渐近符号表示算法的时间复杂度；会用扩展递归技术分析算法时间的复杂性；对于表示算法时间的简单递推式，能够用扩展递归技术求出最终结果。P15：例1.6P18：实验1P22：习题1.7三种渐近符号的含义大O符号：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))大Ω符号：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(

2、g(n))Θ符号：若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))渐近符号表示算法时间复杂度[定理1.1]若T(n)=amnm+am-1nm-1+···a1n+a0(am>0)，则有T(n)=O(nm)，且T(n)=Ω(nm)，从而T(n)=Θ(nm)[例]T(n)＝5n2＋8n＋1当n≥1时，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)当n≥1时，5n2＋8n＋1≥5n2＝Ω(n

3、2)∴当n≥1时，14n2≥5n2＋8n＋1≥5n2则：5n2＋8n＋1＝Θ(n2)用扩展递归技术分析算法时间的复杂性扩展递归技术：将递推关系式中右边项根据递推式进行逐次替换，得到求和表达式[例]第2章NP完全理论对于简单的判定问题，会画判定树。判定树（DecisionTrees）是一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。[例]对三个数进行排序的判定树第3章蛮力法掌握改进的串

4、匹配算法——KMP算法理解n个元素的生成排列对象理解n个元素组成的集合的生成子集理解0/1背包问题理解TSP问题KMP算法KMP算法思路：如果某趟在Si和Tj匹配失败后，指针i不回溯；模式T向右滑动至某个位置k，使得tk对准si继续进行匹配。怎么求k？模式T=“t1t2…tm”中的每一个字符tj都对应一个k，显然k与S无关。用next[j]表示tj对应的k值，则t1…tk-1既是t1…tj-1的真前缀，又是t1…tj-1的真后缀的最长子串，称k是tj的前缀函数值，它等于最长子串长度加1。next数组的定

5、义next数组定义如下：t1t2t3t4t5t6ababac真前缀真后缀∵t1=t5,t1t2t3=t3t4t5∴a和aba都是ababa的真前缀和真后缀，但aba的长度最大∴next[6]=3+1=4，即当t6和si匹配失败后，将t4和si比较一个求k的例子：next数组的求法：已求出next[1],…,next[j]，咋求next[j+1]?设k是t[j]的前缀函数值，从而有t1…t2tk-1=tj-k+1tj-k+2…tj-1比较tk和tj，得2种情况：(1)tk=tj：说明t1…tk-1tk=t

6、j-k+1…tj-1tj，则next[j+1]=k+1；(2)tk≠tj：此时要找出t1…tj-1的后缀中第2大真前缀next[next[j]]=next[k],t1…tnext[k]-1=tj-next[k]+1…tj-1，再比较tnext[k]和tj，又会出现2种情况：next数组的求法：当tnext[k]=tj时，与(1)类似，next[j+1]=next[k]+1；当不等时，找第3大真前缀，重复(2)的过程，直至找到t1…tj-1后缀中的最大真前缀，或确定t1…tj-1的后缀中没有最大真前缀，此

7、时next[j+1]=1。算法3.4KMP算法中求next数组voidGetNext(charT[],intnext[]){//下标从1开始next[1]=0;j=1;k=0;while(j<=m)If((k==0)

8、

9、(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k]}算法3.5KMP算法1.在串S和T中分别设定比较的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如S[i]=T[j]，则继续比较S和T的下一字符；否则2

10、.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，则将i和j分别加1，准备下一趟比较；3.如果T中所有字符均比较完毕，则返回匹配的起始下标，否则返回0。生成排列对象思路：假定已生成了{1,2,…,n-1}的所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列的n个位置中去，得到问题规模为n的所有排列。这时排列总数为n(n-1)!=n!。时间复杂性：O(n!)算法3.9生成排列对象（伪代码）1.生成初始排