算法复习整理(呕心之作).doc

此文档收集于网络，如有侵权，请 联系网站删除算法设计与分析复习提纲 2011.06.121 引言(ch1)1. 什么是算法及其特征算法是通过一系列有限的指令集构成的对特定问题进行求解的计算机执行描述。算法特征：输入、输出、有限性、确定性、通用性2. 问题实例和问题规模问题实例：解决一个问题所需要的所有输入问题规模：算法输入实例的大小2 算法初步(ch2)1. 插入排序算法INSERT_SORT(A) for j-2 to lengthA Do key-Aj/将Aj插入到已排序的数列A1.j-1 i0 and Aikeydo Ai+1-Ai/给Aj腾出位置 i-i-1 Ai+1-key/找到位置插入key2.算法复杂性及其度量 (1)时间复杂性和空间复杂性；一个算法所需要的时间通常和输入的规模成同步增长，所以我们通常把算法运行的时间写成输入规模的某种形式，称为时间复杂度。算法的空间复杂度通常是指算法所需要的内存存储空间的大小的量级，通常也写成输入规模的某种形式。 (2)最坏、最好和平均情形复杂性；算法的最坏运行时间是指在任何输入情况下运行时间的一个上界。最好的复杂度是指在任何输入情况下运行时间的一个下界。平均时间复杂度是指算法运行时间的数学期望。3.插入排序的最坏、最好和平均时间插入排序的最坏时间复杂度是O(n2)发生在输入是逆序的情况下,最好时间复杂度是O(n)发生输入是顺序的情况下。平均时间复杂度同O(n2)。3. 归并排序算法及其时间复杂性MERGE(A,p,q,r)/将两个排好序的数组合并n1 -q-p+1n2-r-q/r-(q+1)+1create arrays L1.n1+1 and R1.n2+1/建立两个数组for i-1 to n1 do Li-Ap+i-1 for j-1 to n2 do Rj-Aq+j/A(q+1)+j-1 Ln1+1-max/Max表示无穷大 Ln2+1-max/用作哨兵 i-1 j-1 for k-p to r do if Li=Rj then Ak-Li i-i+1 else Ak-Rj j-j+1MERGE-SORT(A,p,r)/归并排序采用分治发，分解+解决+合并if pr then qn0时有c1g(n)=f(n)n0时有0=f(n)=cg(n)（注：证明的时候找出n0和c即可，千万不要忘记还要证明0=n0的时候有f(n)=cg(n)成立（注：证明的时候找出符合条件的n0和c即可）2. 标准复杂性函数及其大小关系(1)多项式时间阶的大小O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)(2)指数时间阶的大小O(2n)O(n!)n0时候一切都符合猜测的结论)c.有时候得到T(n)=cn+1的时候需要在猜测解中减去一个低阶项，凑成T(n)=cn(2)变量变换法； 替换使式子变形为已知的熟悉的形式。如T(n)=2T(n/2)+n2.迭代法(1)展开法；关键是处理通项等于1的情况，也就是递归结束的情况。(2)递归树法；主要关注Runing time（同一层上所有节点的时间和） 和size（原来的几分之几）两个指标，选取size最慢到1的分支为标准（分支最长的）。3.主定理Case 3 的时候不要忘记证明af(b/n)=cf(n)对某个c1且足够大的n成立。5 概率分析(ch5)1.雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性方法1：为每个Ai指定一个优先级pi然后按pi对A排序 PermuteBySort()n-lengthA;for(i=1;i=n;i+)pi-Random(1n3);用p作为关键字对A 排序；Return A;时间复杂度：(nlogn)/主要用在排序上，归并排序的时间复杂度是O(nlogn) 方法2：就地枚举 RandomInPlace(A)n-lengthA; for(i=1;i=n;i+) AiARandom(1,n);/直接就地生成优先级后就交换位置 时间复杂度：(n)3.online雇佣问题及其概率分析(略)6 堆排序(ch6)1堆的概念和存储结构堆是一种数据结构它是一种数组对象，可以视为一棵完全二叉树。每一层都是满的，最后一层可能除外。2.堆的性质和种类(1)子节点和父节点下标之间的关系某节点的下标是i，则left(i)=2i,right(i)=2i+1 Parent(i)=(i/2)的下取整。(2)n个节点的堆其叶子节点为(n/2)+1,(n/2)+2n3.堆的操作：建堆；整堆；建堆操作是建立在整堆基础上的，整堆的原理是：假设i的以左孩子为根的子树和以右孩子为根的子树均为整好堆的大根堆，需要将i节点的值与left(i)和right(i)节点的值做比较，如果i节点值最大则无需整堆已经是大顶堆,如果不是则找出左右孩子的最大值并交换i节点和子孩子节点的值，由于交换的过程中可能破坏了该子树的大顶堆的性质，则需要从该子节点开始继续整堆，是个递归的过程。MAX-HEAPIFY(A,i)l-left(i)r-right(i)if lAithen largest-lelse largest-iif rAlargestthen largest-rif laresti then do exchange AiAlargestMAX-HEAPIFY(A,largest)时间复杂度：O(logn)建堆：从lengthA/2处开始整堆，直至树根。BUILD-MAX-HEAPIFY(A)heap-sizeA-lengthAfor i-lengthA/2 downto 1do MAX-HEAPIFY(A,i)时间复杂度：O(n)/O(nlogn)为其非紧致界4.堆排序算法和时间复杂性堆排序算法的思想是：先交换、再整堆、再交换、在执行的过程中，始终保持该堆为大顶堆。HEAPSORT(A)BUILD-MAX-HEAP(A);/建堆O(n) for i-lengthA downto 2/循环整堆+断裂O(nlogn)doexchange A1Ai heap-sizeA-heap-sizeA-1MAX-HEAPIFY(A,1)时间复杂度为：O(n+nlogn)5.优先队列及其维护操作(1)插入操作MAX-HEAP-INSERT(A,key) heap-sizeA+;i1 and Ai.parentkey) do Ai-Aparenti; i-parenti;Ai-key;时间复杂度为O(logn) (2)取最大关键字Return A1;/时间O(1) (3)删除堆顶元素（出队）HEAP-EXTRACT-MAX(A) if heap-sizeA1 then return “Over Flow”; MAX-A1; A1Aheap-sizeA; heap-sizeA-; MAX-HEAPIFY(A,1)/O(logn)/显然时间复杂度为O(logn)(4)增值HEAP-INCRESE-KEY(A,i,key)/将Ai增至key if(Ai=key)/往下调整 then Ai1 and Aparentikey) doAi-Aparenti i-parenti Ai-key时间复杂度为O(logn)总结：所有的优先队列的维护操作均可以在O(logn)时间内完成。7 快速排序(ch7)1. 快速排序算法及其最好、最坏时间和平均时间快速排序采用分治法，把问题分为更小的规模，每次划分都调用一个算法生成一个划分源q将数组Ap.r分成Ap.q-1 、Aq、Aq+1.r三部分QuickSort(A,p,r)/对Ap.r快排序if(pr) then/递归到p=r时结束q-Partition(A,p,r);/生成划分源QuickSort(A,p,q-1);/子问题1QuickSort(A,q+1,r);/子问题2Partition(A,p,r)/划分源生成算法1，选取Ar为划分源，使其左边元素小于它，右边元素大于它x-Ar;i-p-1;for(j=p;j=r-1;j+)/始终保持Ap.i中的元素小于Arif(xAr)i-i+1;AiAj;Ai+1Ar;/Ar就位return i+1;/返回q快速排序实际上是一个就地（Inplace）排序。性能分析：（1） 最坏的划分：Ap.q-1,Aq+1,r有一个是空的T(n)=T(n-1)+T(0)+(n)/数组最后一个元素是最大的情况（做为划分源），前面是n-1个元素，后面元素个数为0。(n)为生成划分源的时间。由迭代法：T(n)= (n2)（2） 最好的划分：比较平均，两部分一样大T(n)=2T(n/2)+ (n)/一个大小为n/2,另一个为n/2-1,规模小于2T(n/2)由master定理的case2可知T(n)= O(nlogn)(3)平衡的划分，每次划分保持固定比例，其运行时间接近最好的划分为O(nlogn)，只要按照固定比例划分，得到的时间复杂度都是O(nlogn)2. 随机快速排序算法及其期望时间随机快速排序要求每次的划分源随机产生只需改动partition为RandomizedPartion(A,p,r)j-Random(p,r);/随机在Ap.r中选择元素作为划分源ArAi;/将Ai交换到最后，因为partition是以最后元素作为划分源的Return Parition(A,p,r);/返回划分源q期望时间为1.44nlogn(knuth时间分析)，为O(nlogn)。8 线性时间排序(ch8)1. 基于比较的排序算法下界：(nlogn)可以用判定树进行说明。2. 计数排序适应的排序对象、算法和时间适应的排序对象：一列有相同元素或没有相同元素的整数数列。元素互不相同时的算法：SpecialCountingSort(A,B)/B1.n为排序结果for i1 to n doBAiAi; /如Ai=5，就放到B5中，小于5的元素不超过5个。时间：O(n) ，无比较，当数组不是连续的整数时比较浪费空间。有相同元素时的算法：CountingSort(A,B,k)/B1.n为排序结果，C1.k为计数数组for i1 to k do Ci0;for j1 to lengthA do /扫描A，值相同元素计数CAj+;for i2 to k do /Ci修改，累计计数CiCi+Ci-1;for jlengthA downto 1 do BCAjAj;CAj-;时间：T(n,k)=(n+k)=(n) ，如果k=(n)时3. 基数排序适应的排序对象、算法和时间适应的排序对象：用k进制表示为不超过d位数的整数序列。算法：RadixSort(A,d) for i1 to d do使用稳定的排序算法对A的第i位排序；/如计数排序时间：T(n)=(d(n+k) /k为基，d为位数4. 桶排序适应的排序对象、算法和时间适应的对象：均匀分布在0,1)上的实数列。算法描述：BucketSort(A) nlengthA;for i1 to n do /扫描A，时间为(n)将Ai插入到链表BnAi中;for i0 to n-1 do/时间为(n)*用插入排序将Bi排序;将B0, B1, Bn-1连接起来;/时间为(n)*注： n个数是均匀分布在0,1)中， 每个桶中大约只有一个数， 时间为O(1)9 中位数和顺序统计(ch9)1. 最大和最小值的求解方法方法一：分别独立求，比较次数为(n-1)+(n-2)=2n-3次方法二：成对输入x,y每对比较三次 比较x, y； 将min(x, y)与当前最小值比较； 将max(x, y)与当前最大值比较；总比较次数约为3 n/2 。/第一对元素比较一次，最后一组元素若为一个，至多比较二次2. 期望时间为线性的选择算法利用快排序的随机划分法，进行问题的划分 划分Ap.r Ap.q-1AqAq+1.r ；/ Aq为划分元 kq-p+1； /即Aq是第k个最小元 if (i=k) then / k = 左区间长度+1return Aq；if (ik) then 在左区间中继续找第i个元素；if (ik) then 在右区间中继续找第i-k个元素；临界条件：当区间长度为1时，直接返回该元素RandomizedSelect(A, p, r, i) /选择ith元素if p=r then return Ap;/处理临界条件qRandomizedPartition(A, p, r);/随机产生划分源kq-p+1; /Aq是第k小的元素if i=k thenreturn Aq; /Aq是第i小元素else if ik then /第i小元素落在左区间return RandomizedSelect(A, p, q-1, i);else/第i小元素落在右区间return RandomizedSelect(A, q+1, r, i-k);最好：每次划分为相等的左右区间T(n)=T(n/2)+n T(n)=(n)/由master定理的case3最坏：每次划分为不均等的左右区间T(n)=T(n-1)+n T(n)=(n2)/由迭代法平均(期望)：分析略。T(n)=(n)/平均时间期望同最好情况3. 最坏时间为线性的选择算法及其时间分析While n1 dostep 1. 将n个元素分成5个1组，共n/5组。其中最后1组有n mod 5个元素。/O(1)step 2. 用插入排序对每组排序，取其中值。若最后1组有偶数个元素，取较小的中值。/O(1)step 3. 递归地使用本算法找找n/5个中值的中值x。/T(n/5)step 4. 用x作为划分元对A数组进行划分，并设x是第k个/O(n)最小元。step 5. if i=k then return x;/至多T(7n/10+6)else if i140， 有n/(n-70)2 取c20a -cn/10+7c+an0故T(n)=O(n)10 递归与分治法(sch1)1. 递归设计技术把问题划分为更小规模的和原问题同等问题的子问题，子问题解决了，原问题就解决了2. 递归程序的非递归化用栈消除递归利用迭代法消除递归末尾递归消除法3.算法设计 (1)Fibonacci数；Fibonacci(n) /递归算法if n=0 or n=1 thenreturn n;elsereturn Fibonacci(n-1) + Fibonacci(n-2) ;Fibonacci(n) /非递归算法if n=0 or n=1 thenreturn n;s1 = 0; s2 = 1;for i2 to n dosums1 + s2;s1s2;s2sum;return sum;(2)生成全排列； 问题分析- 分解：将原问题分解为n个子问题，子问题1：生成n-1个元素s1,sn-1的全排列后接sn;子问题2：生成n-1个元素s1,sn-2,sn的全排列后接sn-1; 子问题n：生成n-1个元素s2,sn的全排列后接s1;- 递归求解：子问题与原问题的性质相同，只不过规模为n-1。设原问题的求解算法为permute(s,n)，则子问题就是递归调用permute(s,n-1)。临界条件：一个元素的排列就是该元素本身。算法Permute( s, n ) /n个元素s1.n, 输出所有的排列if n=1 thenprint(s); /输出s的一个排列else Permute(s, n-1); /第一个子问题求解，不需要交换snfor in-1 downto 1 do swap(si, sn); /交换si, sn，后接Sn-1到S1Permute(s, n-1);swap(si, sn); /交换si, sn, 使s恢复原状(3)二分查找； 注：T(n)可由master定理的case2得到(4)大整数乘法；由master定理的case1注：四次n/2位乘法是AC,AD,BC,BD。注：同样T(n)可由master定理的case1得到，通过将AD+BC用(（A-B）(D-C)+AC+BD)表示减少了一次n/2位的乘法(5)Stranssen矩阵乘法； 乘法次数从8次减为7次。 同样T(n)由master定理的case1获得。(6)导线和开关(略)；11 动态规划(ch15)1.方法的基本思想和基本步骤 动态规划的思想实质是分治思想和解决冗余。基本步骤：找出最优解的性质，并刻画其结构特征；递归地定义最优值（写出动态规划方程）；以自底向上的方式计算出最优值；根据计算最优值时记录的信息，构造最优解。注：步骤是动态规划算法的基本步骤。如果只需要求出最优值的情形，步骤可以省略；若需要求出问题的一个最优解，则必须执行步骤，步骤中记录的信息是构造最优解的基础2.动态规划和分治法求解问题的区别经分解的子问题往往不是互相独立的，通常会在计算过程中保存已解决的子问题的答案，在需要时再查找，动态规划法用一个表来记录所有已解的子问题的答案。3.最优性原理及其问题满足最优性原理的证明方法求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。注：对具有最优性原理性质的问题而言，如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。证明多用反正法，假设它的子问题不是最有的可以得到它本身也不是最优的矛盾结论。4.算法设计(1)多段图规划； 其中k为顶点集合数。 算法如下： (2)矩阵链乘法； T(n)=O(n3), S(n)=O(n2)(4) 最大子段和； 直接算法：T(n)=O(n2) 分治算法：T(n)=O(nlogn) 动态规划算法：T(n)=O(n) bj表示所有下标以j结束的最大子段和如果bj是最大子段和，那么bj-1一定也是最大子段和。(4)最长公共子序列；12 贪心算法(ch16)1.方法的基本思想和基本步骤基本思想：从问题的某一个初始解出发，通过一系列的贪心选择当前状态下的局部最优选择，逐步逼近给定的目标，尽可能快地求得更好的解。其中贪心点的选取是关键的步骤。求解步骤：从问题的某一初始解出发；while 依据贪心策略朝给定目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；2.贪心算法的正确性保证：满足贪心选择性质贪心算法的正确性，就是要证明按贪心准则求得的解是全局最优解。3.贪心算法与动态规划的比较(1)动态规划的每一次选择都依赖于子问题的解决，而贪心法会快速选择当前看起来解决问题最好的办法。(2)动态规划要先解决子问题，而贪心法可以在解决子问题之前做出选择。(3)动态规划是自底向上的，而贪心法是自顶向下的。(4)动态规划法通常教复杂，运行较慢，而贪心法较简单，运行较快。4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质两种背包问题都满足最优子结构性质，都可以用动态规划来求解；小数背包问题还具有贪心选择性质，用贪心法求解更简单、更快速。但0-1背包问题用贪心法求解不一定能得到最优解。5.算法设计 (1)小数背包；按价值率（价值/重量）最大贪心，使单位重量价值增长最快。 时间主要花在排序上。 (2)活动安排；贪心策略设各活动已按结束时间排序：f1f2fn，先选出活动1，然后按活动编号从小到大的次序依次选择与当前活动相容的活动。注：这种策略使剩余的可安排时间极大化，以便于安排尽可能多的相容活动。(3)找钱问题(略)；13 回溯法(sch2)1. 方法的基本思想和基本步骤基本思想： 在问题的解空间中从根节点按照深度优先的方法搜索解空间树，在遇到死节点时果断跳过。基本步骤：（1） 定义问题的解空间（对问题的解进行编码）（2） 用树或图表示解空间的结构（3） 深度优先遍历解空间并果断跳过死节点的子树。2.回溯法是一种深度遍历的搜索3.术语: 三种搜索空间, 活结点, 死结点, 扩展结点, 开始结点, 终端结点三种搜索空间：- 表序表示: 搜索对象用线性表数据结构表示;- 显式图表示: 搜索对象在搜索前就用图(树)的数据结构表示;- 隐式图表示: 除了初始结点, 其他结点在搜索过程中动态生成. 缘于搜索空间大, 难以全部存储.活节点：当前正在访问的节点扩展节点：指可以以该节点为出发点继续遍历的节点死节点：指在该节点处无法再纵深扩展的节点。开始节点：通常指解空间的根节点终端节点：解空间的叶节点3. 两种解空间树和相应的算法框架子集树：如0-1背包，叶结点数2n，总结点数2n+1，遍历时间为(2n)；排列树：如TSP问题，叶结点数n!，遍历时间为(n!)。注：遍历过程中可通过限界（如当前计算的结果已经比前面计算的结果更不可接受）来剪掉不可能得到最优解的子树，通过约束条件剪掉不符合约束条件的子树（如0-1背包问题的背包容量）。 算法框架：5.算法设计 (1)图和树的遍历；注：先序遍历的递归用栈模拟实现，先访问跟然后右孩子压栈访问左孩子当直到p=nil的时候右孩子出栈对其进行访问，再访问右孩子的左孩子，右孩子的右孩子压栈，如此往复直到栈为空。注：层次遍历用队列进行模拟，根节点出队列的时候其左孩子和右孩子依次入栈，如此往复。注：与树的层次优先遍历算法类似(2)n后问题； (3)0-1背包；注：回溯之后要减去当前的重量和价值（可对照树的回溯操作过程）。 (4)排列生成问题；算法理解：要对从1开始的数列形成全排列，则先在不交换的情况下从2开始生成全排列+1即可，然后交换1和2的位置从2开始生成全数列，生成后交换回来，再交换1和3的位置，从2开始生成全数列。同理，要对从2开始的数列形成全排列，先不交换2和3的位置从3开始形成全排列+2即可，然后交换2和3的位置再从3开始形成全排列，之后交换回来。要对从3开始的数列形成全排列，则直接输出即可。(5) TSP问题；基本思想：利用排列生成问题的回溯算法Backtrack(2)，对x=1,2,n的x2.n进行全排列，则(x1,x2),(x2,x3), , (xn,x1)构成一个回路。在全排列算法的基础上，进行路径计算保存以及进行限界剪枝。cc+=axi-1xi;表示把当前节点当成最短路径上的点。cc-=axi-1xi;表示回溯后取消最短路径上的当前点，尝试其他可能。14 分枝限界法(sch3)1.方法的基本思想和基本步骤基本思想：在解空间树中, 以广度优先BFS或最佳优先方式搜索最优解, 利用部分解的最优信息, 裁剪那些不能得到最优解的子树以提高搜索效率。基本步骤：定义解空间(对解编码);确定解空间的树结构;按BFS等方式搜索:a.每个活结点仅有一次机会变成扩展结点；b.由扩展结点生成一步可达的新结点；c.在新结点中, 删除不可能导出最优解的结点； /限界策略d.将余下的新结点加入活动表(队列)中；e.从活动表中选择结点再扩展； /分支策略f.直至活动表为空；2. 与回溯法的区别(1)求解目标不同，回溯发通常会求出满足约束条件的所有解而分支限界法却只要尽快找到满足条件的一个解(2)搜索方式不同，回溯法采用深度优先而分支限界法采用广度优先或最佳优先。(3)对节点的扩展方式不同,分支限界法任何节点只有一次机会成为扩展节点，活节点一旦成为扩展节点，则一次性产生其所有子节点。(4)存储空间不同，分支限界法通常需要大量的存储空间。3.活结点的两种扩展方式(1)先进先出队列（F I F O） : 从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同；(2)优先队列（耗费用小根堆,受益用大根堆）: 每个结点都有一个对应的耗费或收益。-如果查找一个具有最小耗费的解，则活结点表可用小根堆来建立，下一个扩展结点就是具有最小耗费的活结点；-如果希望搜索一个具有最大收益的解，则可用大根堆来构造活结点表，下一个扩展结点是具有最大收益的活结点。4.0-1背包问题的搜索: FIFO队列和优先队列问题： 0-1背包问题:物品数n=3, 重量w=(20,15,15),价值v=(40,25,25), 背包容量c=30, 试装入价值和最大的物品?注：当前节点出队列的时候按照广度优先将其孩子节点入队。注：价值率高的优先扩展5.算法设计 (1)8-迷问题(略)； (2)装载问题(略)；15 数论算法(ch31)1. gcd(a, b)及其表示成a, b线性组合方法gcd(a,b)=ax+by中最小的数2. Euclids Alg.的运行时间Euclid(a, b) if b=0 thenreturn a;elsereturn Euclid(b, a mod b);注:- Euclids Alg.递归调用的次数为O(logb)- 算法应用到二个位整数上，算法耗费O()算术运算和O(3)位运算3.线性模方程的求解方法对线性模方程axb(mod n)(1) 调用EXTENDED_EUCLID(a,n)得出(d,x,y)的值(2) 求出特征解x0=x(b/d)(mod n)(3) 求出全解 xi=x0+i(n/d) (mod n)其中0=i=d-13. 中国余数定理及其相应线性同余方程组的求解对形如：x a1 ( mod n1)x a2 ( mod n2)x ak ( mod nk)的模方程组(1) m1=n2*n3*.*nK(即缺少n1的连乘)m2=n1*n3*.*nkm3=n1*n2*n4.*nkmk-1=n1*n2*n3.*nk-2*nK-1mk=n1*n2*n3.*nK-1(2) c1=m1(m1-1mod n1) c2=m2(m2-1mod n2) ck=mk(mk-1mod nk) (3)x=c1a1+c2a2+ckak（mod n1*n2*.*nk）5.RSA算法(略)6.简单素数测试算法和伪素数测试算法PseudoPrime(n) if ModularExponentiation(2,n-1,n) ! 1 (mod n) thenreturn Composite;elsereturn Prime;即验证2(n-1)=1 (mod n)是否满足，若满足则可能为素数，不满足一定为合数注:- 该算法判断出合数总是正确的;- 如果算法给出的结论是素数，仅在基2的伪素数情形出错。7.MR算法的改进措施和算法复杂性算法的复杂性设n为-bit整数，算法需要O(s)算术运算、O(3)位运算 算法的误判率- Th31.38n为奇合数，则n的Witness数大于(n-1)/2- Th31.39MR算法的误判率不超过2-s16 串匹配(ch32)1.朴素的串匹配算法及其时间复杂度NAVE-STRING-MATCHER (T, P)n lengthTm lengthPfor s 0 to n-mif P1.m = T (s+1).(s+m)print “pattern occurs with shift” sSo, the worst-case running time is (n-m+1)m) but average-case is O(n+m),Also works well in practice.2. Rabin-Karp串匹配算法及其时间复杂度 For each hit, i.e., for each s where ts p (mod q), verify character by character whether s is a valid shift or a spurious hit In the worst case, every shift is verified Running time can be shown as O(n-m+1)m) Average-case running time is O(n+m)3.有限自动机串匹配算法及其时间复杂度Input: Text string T 1.n, and mResult: All valid shifts displayedFINITE-AUTOMATON-MATCHER (T, m, )n lengthTq 0for i 1 to nq (q, T i)if q = mprint “pattern occurs with shift” i-m String matching is efficient: (n) Each character is examined exactly once Constant time for each character But time to compute is O(m |) Has O(m | ) entries该有限自动机的建立时间为O(m |)=O(7*3)4. KMP串匹配算法及其时间复杂度ababaabaPqPkCompare pattern against itself; longest prefix of P that is also a suffix of P5 is P3; so 5= 3q1234567pababaca0012301q = max k | kq and Pk is a suffix of Pq KMP Algorithm 2 parts: KMP-MATCHER, PREFIX Running time PREFIX takes O(m) KMP-MATCHER takes O(m+n)17 随机算法(sch4)1. 随机算法的定义定义：是一个概率图灵机. 也就是在算法中引入随机因素, 即通过随机数选择算法的下一步操作。2. 随机算法的分类： Las Vegas和Monte CarloLas Vegas算法运行结束时总能给出正确的解，但其运行时间每次有所不同。Monte Carlo算法可能得到不正确的结果，但这种概率是小的且有界的。(1)QuickSort属于Las Vegas类型；不同的划分会导致不同的运行时间 (2)MinCut属于Monte Carlo类型；随机重复k次可能无法找到两定点之间最少的边数。3.一般设计风范(略)4.算法设计 (1)随机取样；T(n)=(n) (2)随机串匹配；18 计算模型和NP完全(ch34)1.算法的严格定义现在严格地讲，一个问题算法可解的等于该问题在图灵机上可解(可判断)。2.几种计算模型的语言识别能力有限状态自动机能够识别正则文法生成的语言；下推自动机能够识别上下文无