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

算法分析与设计 常熟理工学院计算机学院 刘在德 第1章 绪论 掌握三种渐近符号（O、Ω 、Θ ）的含义； 会用三种渐近符号表示算法的时间复杂度； 会用扩展递归技术分析算法时间的复杂性；对于表示算法时间的简单递推式，能够用扩展递归技术求出最终结果。 P15：例1.6 P18：实验1 P22：习题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)=Ω(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 (am0)，则有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＝Ω(n2)∴ 当n≥1时，14n2≥5n2＋8n＋1≥5n2则：5n2＋8n＋1＝Θ(n2) 用扩展递归技术分析算法时间的复杂性 扩展递归技术：将递推关系式中右边项根据递推式进行逐次替换，得到求和表达式 [例] 第2章 NP完全理论 对于简单的判定问题，会画判定树。 判定树（Decision Trees）是一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。 [例] 对三个数进行排序的判定树 第3章 蛮力法 掌握改进的串匹配算法——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数组的定义 next数组定义如下： 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=tj-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的后缀中没有最大真前缀，此时next[j+1]=1。 算法3.4 KMP算法中求next数组 void GetNext (char T[ ], int next[ ]) { // 下标从1开始 next[1] = 0; j=1; k=0; while (j = m) If ((k==0) || (T[j]==T[k])) { j++; k++; next[j]=k; } else k=next[k] } 算法3.5 KMP算法 1. 在串S和T中分别设定比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如S[i]=T[j]，则继续比较S和T的下一字符；否则 2.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!