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

《算法设计与分析》复习提纲1引言(ch1)什么是算法及其特征算法是通过一系列有限的指令集构成的对特定问题进行求解的计算机执行描述。算法特征：输入、输出、有限性、确定性、通用性问题实例和问题规模问题实例：解决一个问题所需要的所有输入问题规模：算法输入实例的大小2算法初步(ch2)插入排序算法INSERT_SORT(A) forj<-2tolength[A]Dokey<-A[j]//将A[j]插入到已排序的数列A[1..j-1] i<-j-1 whilei>0andA[i]>key doA[i+1]<-A[i]//给A[j]腾出位置i<-i-1A[i+1]<-key//找到位置插入key2.算法复杂性及其度量(1)时间复杂性和空间复杂性；一个算法所需要的时间通常和输入的规模成同步增长，所以我们通常把算法运行的时间写成输入规模的某种形式，称为时间复杂度。算法的空间复杂度通常是指算法所需要的内存存储空间的大小的量级，通常也写成输入规模的某种形式。(2)最坏、最好和平均情形复杂性；算法的最坏运行时间是指在任何输入情况下运行时间的一个上界。最好的复杂度是指在任何输入情况下运行时间的一个下界。平均时间复杂度是指算法运行时间的数学期望。3.插入排序的最坏、最好和平均时间插入排序的最坏时间复杂度是O(n2)发生在输入是逆序的情况下,最好时间复杂度是O(n)发生输入是顺序的情况下。平均时间复杂度同O(n2)。归并排序算法及其时间复杂性MERGE(A,p,q,r)//将两个排好序的数组合并 n1<-q-p+1 n2<-r-q//r-(q+1)+1createarraysL[1..n1+1]andR[1..n2+1]//建立两个数组fori<-1ton1doL[i]<-A[p+i-1]forj<-1ton2doR[j]<-A[q+j]//A[(q+1)+j-1]L[n1+1]<-max//Max表示无穷大L[n2+1]<-max//用作哨兵i<-1j<-1fork<-ptordoifL[i]<=R[j]thenA[k]<-L[i]i<-i+1elseA[k]<-R[j]j<-j+1MERGE-SORT(A,p,r)//归并排序采用分治发，分解+解决+合并 ifp<rthenq<-(p+r)/2//下取整，分解MERGE-SORT(A,p,q)//解决一半MERGE-SORT(A,q+1,r)//解决另一半MERGE(A,p,q,r)//合并时间复杂度为O(nlogn)3函数增长率(ch3)渐近记号O、Ω、θ的定义及其使用θ:渐紧界，即存在n0,c1,c2,当n>n0时有c1g(n)=<f(n)<=c2O:渐进上界，即存在n0,c当n>n0时有0=<f(n)<=cg(n)（注：证明的时候找出n0和c即可，千万不要忘记还要证明0=<f(n)的情况，会影响n0的取值）Ω：渐进下界，即存在n0,c,当n>n0的时候有f(n)>=cg(n)成立（（注：证明的时候找出符合条件的n0和c即可）标准复杂性函数及其大小关系(1)多项式时间阶的大小O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)……(2)指数时间阶的大小O(2n)<O(n!)<O(nn)和式界的证明方法数学归纳法，先猜，后用数学归纳法按照界的证明方法证明（求c和n0）对项进行限界：利用最大、最小值进行放缩，以及利用和式的前后两项比值小于1进行几何级数的限界。和式分解简单的分解忽略和式初始几项更复杂的划分，要充分考虑和式的规律性积分近似（分为f(k)单调递增和递减两种情况）可用于求紧致界Knuth求和的七种方法4递归关系式(ch4)1.替换法(1)猜测解数学归纳法证明；注：a.出现T(n/2)的情况下要假设T(n/2)符合条件，继而得到T(n)符合条件b.不要忘记证明归纳基础(n=1、n=2直到找到一个n0，使得对n>n0时候一切都符合猜测的结论)c.有时候得到T(n)<=cn+1的时候需要在猜测解中减去一个低阶项，凑成T(n)<=cn(2)变量变换法；替换使式子变形为已知的熟悉的形式。如T(n)=2T(n/2)+n2.迭代法(1)展开法；关键是处理通项等于1的情况，也就是递归结束的情况。(2)递归树法；主要关注Runingtime（同一层上所有节点的时间和）和size（原来的几分之几）两个指标，选取size最慢到1的分支为标准（分支最长的）。3.主定理Case3的时候不要忘记证明af(b/n)<=cf(n)对某个c<1且足够大的n成立。5概率分析(ch5)1.雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性方法1：为每个A[i]指定一个优先级p[i]然后按p[i]对A排序PermuteBySort(){n<-length[A];for(i=1;i<=n;i++)p[i]<-Random(1~n3);用p作为关键字对A排序；ReturnA;

}时间复杂度：θ(nlogn)//主要用在排序上，归并排序的时间复杂度是O(nlogn)方法2：就地枚举RandomInPlace(A) {n<-length[A];for(i=1;i<=n;i++)A[i]<->A[Random(1,n)];//直接就地生成优先级后就交换位置}时间复杂度：θ(n)3.online雇佣问题及其概率分析(略)6堆排序(ch6)1堆的概念和存储结构堆是一种数据结构它是一种数组对象，可以视为一棵完全二叉树。每一层都是满的，最后一层可能除外。2.堆的性质和种类(1)子节点和父节点下标之间的关系某节点的下标是i，则left(i)=2i,right(i)=2i+1Parent(i)=(i/2)的下取整。(2)n个节点的堆其叶子节点为(n/2)+1,(n/2)+2……n3.堆的操作：建堆；整堆；建堆操作是建立在整堆基础上的，整堆的原理是：假设i的以左孩子为根的子树和以右孩子为根的子树均为整好堆的大根堆，需要将i节点的值与left(i)和right(i)节点的值做比较，如果i节点值最大则无需整堆已经是大顶堆,如果不是则找出左右孩子的最大值并交换i节点和子孩子节点的值，由于交换的过程中可能破坏了该子树的大顶堆的性质，则需要从该子节点开始继续整堆，是个递归的过程。MAX-HEAPIFY(A,i){l<-left(i)r<-right(i)ifl<=heap-size[A]andA[l]>A[i]thenlargest<-lelselargest<-iifr<=heap-size[A]andA[r]>A[largest]thenlargest<-riflarest≠ithendoexchangeA[i]<->A[largest]MAX-HEAPIFY(A,largest)

}时间复杂度：O(logn)建堆：从length[A]/2处开始整堆，直至树根。BUILD-MAX-HEAPIFY(A)heap-size[A]<-length[A]fori<-length[A]/2downto1 doMAX-HEAPIFY(A,i)时间复杂度：O(n)//O(nlogn)为其非紧致界4.堆排序算法和时间复杂性堆排序算法的思想是：先交换、再整堆、再交换、在执行的过程中，始终保持该堆为大顶堆。HEAPSORT(A) BUILD-MAX-HEAP(A);//建堆O(n)fori<-length[A]downto2//循环整堆+断裂O(nlogn) doexchangeA[1]<->A[i] heap-size[A]<-heap-size[A]-1 MAX-HEAPIFY(A,1)时间复杂度为：O(n+nlogn)5.优先队列及其维护操作(1)插入操作 MAX-HEAP-INSERT(A,key){heap-size[A]++;i<-heap-size[A];while(i>1andA[i].parent<key)do {A[i]<-A[parent[i]];i<-parent[i];}A[i]<-key;}时间复杂度为O(logn)(2)取最大关键字ReturnA[1];//时间O(1)(3)删除堆顶元素（出队） HEAP-EXTRACT-MAX(A) {ifheap-size[A]<1thenreturn“OverFlow”;MAX<-A[1];A[1]<->A[heap-size[A]];heap-size[A]--;MAX-HEAPIFY(A,1)//O(logn)}//显然时间复杂度为O(logn)(4)增值HEAP-INCRESE-KEY(A,i,key) {//将A[i]增至keyif(A[i]>=key)//往下调整 thenA[i]<-keyMAX-HEAPIFY(A,i)else//往上调整while(i>1andA[parent[i]]<key)do A[i]<-A[parent[i]]i<-parent[i]A[i]<-key}时间复杂度为O(logn)总结：所有的优先队列的维护操作均可以在O(logn)时间内完成。7快速排序(ch7)快速排序算法及其最好、最坏时间和平均时间快速排序采用分治法，把问题分为更小的规模，每次划分都调用一个算法生成一个划分源q将数组A[p..r]分成A[p..q-1]、A[q]、A[q+1..r]三部分QuickSort(A,p,r){//对A[p..r]快排序if(p<r)then//递归到p=r时结束{q<-Partition(A,p,r);//生成划分源QuickSort(A,p,q-1);//子问题1QuickSort(A,q+1,r);//子问题2}

}Partition(A,p,r)//划分源生成算法1，选取A[r]为划分源，使其左边元素小于它，右边元素大于它{x<-A[r];i<-p-1;for(j=p;j<=r-1;j++){//始终保持A[p..i]中的元素小于A[r]if(x<A[r]){i<-i+1;A[i]<->A[j];}}A[i+1]<->A[r];//A[r]就位returni+1;//返回q}快速排序实际上是一个就地（Inplace）排序。性能分析：最坏的划分：A[p..q-1],A[q+1,r]有一个是空的T(n)=T(n-1)+T(0)+θ(n)//数组最后一个元素是最大的情况（做为划分源），前面是n-1个元素，后面元素个数为0。θ(n)为生成划分源的时间。由迭代法：T(n)=θ(n2)最好的划分：比较平均，两部分一样大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)随机快速排序算法及其期望时间随机快速排序要求每次的划分源随机产生只需改动partition为RandomizedPartion(A,p,r){j<-Random(p,r);//随机在A[p..r]中选择元素作为划分源A[r]<->A[i];//将A[i]交换到最后，因为partition是以最后元素作为划分源的ReturnParition(A,p,r);//返回划分源q

}期望时间为1.44nlogn(knuth时间分析)，为O(nlogn)。8线性时间排序(ch8)基于比较的排序算法下界：Ω(nlogn)可以用判定树进行说明。计数排序适应的排序对象、算法和时间适应的排序对象：一列有相同元素或没有相同元素的整数数列。元素互不相同时的算法：SpecialCountingSort(A,B){//B[1..n]为排序结果fori←1tondo B[A[i]]←A[i];//如A[i]=5，就放到B[5]中，小于5的元素不超过5个。}时间：O(n)，无比较，当数组不是连续的整数时比较浪费空间。有相同元素时的算法：CountingSort(A,B,k){//B[1..n]为排序结果，C[1..k]为计数数组fori←1tokdoC[i]←0;forj←1tolength[A]do//扫描A，值相同元素计数C[A[j]]++;fori←2tokdo//C[i]修改，累计计数C[i]←C[i]+C[i-1];forj←length[A]downto1do{B[C[A[j]]]←A[j];C[A[j]]--;}}时间：T(n,k)=θ(n+k)=θ(n)，如果k=θ(n)时基数排序适应的排序对象、算法和时间适应的排序对象：用k进制表示为不超过d位数的整数序列。算法：RadixSort(A,d){fori←1toddo使用稳定的排序算法对A的第i位排序；//如计数排序}时间：T(n)=θ(d(n+k))//k为基，d为位数桶排序适应的排序对象、算法和时间适应的对象：均匀分布在[0,1)上的实数列。算法描述：BucketSort(A){n←length[A];fori←1tondo//扫描A，时间为θ(n)将A[i]插入到链表B[⎣nA[i]⎦]中;fori←0ton-1do//时间为θ(n)*用插入排序将B[i]排序;将B[0],B[1],…,B[n-1]连接起来;//时间为θ(n)}*注：∵n个数是均匀分布在[0,1)中，∴每个桶中大约只有一个数，∴时间为O(1)9中位数和顺序统计(ch9)最大和最小值的求解方法方法一：分别独立求，比较次数为(n-1)+(n-2)=2n-3次方法二：成对输入x,y每对比较三次①比较x,y；②将min(x,y)与当前最小值比较；③将max(x,y)与当前最大值比较；总比较次数约为3⎣n/2⎦。//第一对元素比较一次，最后一组元素若为一个，至多比较二次期望时间为线性的选择算法利用快排序的随机划分法，进行问题的划分①划分A[p..r]⇒A[p..q-1]≤A[q]＜A[q+1..r]；//A[q]为划分元②k←q-p+1；//即A[q]是第k个最小元③if(i=k)then//k=左区间长度+1returnA[q]；if(i＜k)then在左区间中继续找第i个元素；if(i＞k)then在右区间中继续找第i-k个元素；临界条件：当区间长度为1时，直接返回该元素RandomizedSelect(A,p,r,i){//选择ith元素ifp=rthenreturnA[p];//处理临界条件q←RandomizedPartition(A,p,r);//随机产生划分源k←q-p+1;//A[q]是第k小的元素ifi=kthenreturnA[q];//A[q]是第i小元素elseifi＜kthen//第i小元素落在左区间returnRandomizedSelect(A,p,q-1,i);else//第i小元素落在右区间returnRandomizedSelect(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)//平均时间期望同最好情况最坏时间为线性的选择算法及其时间分析Whilen＞1dostep1.将n个元素分成5个1组，共⎡n/5⎤组。其中最后1组有nmod5个元素。//O(1)step2.用插入排序对每组排序，取其中值。若最后1组有偶数个元素，取较小的中值。//O(1)step3.递归地使用本算法找找⎡n/5⎤个中值的中值x。//T(⎡n/5⎤)step4.用x作为划分元对A数组进行划分，并设x是第k个//O(n)最小元。step5.ifi=kthenreturnx;//至多T(7n/10+6)elseifi<kthen找左区间的第i个最小元;else找右区间的第i-k个最小元;用替代法证：T(n)≤cnT(n)≤c⎡n/5⎤+c(7n/10+6)+an//a为常数≤c(n/5+1)+c(7n/10+6)+an=cn/5+c+7cn/10+6c+an=9cn/10+7c+an=cn+(-cn/10+7c+an)≤cn//if-cn/10+7c+an≤0要使-cn/10+7c+an≤0，只要c≥10an/(n-70)∵假定n>140，∴有n/(n-70)＜2∴取c≥20a⇒-cn/10+7c+an≤0故T(n)=O(n)10递归与分治法(sch1)递归设计技术把问题划分为更小规模的和原问题同等问题的子问题，子问题解决了，原问题就解决了递归程序的非递归化=1\*GB3①用栈消除递归=2\*GB3②利用迭代法消除递归=3\*GB3③末尾递归消除法3.算法设计(1)Fibonacci数；Fibonacci(n){//递归算法ifn=0orn=1thenreturnn;elsereturnFibonacci(n-1)+Fibonacci(n-2);}Fibonacci(n){//非递归算法ifn=0orn=1thenreturnn;s1=0;s2=1;fori←2tondo{sum←s1+s2;s1←s2;s2←sum;}returnsum;}(2)生成全排列；问题分析-分解：将原问题分解为n个子问题，子问题1：生成n-1个元素s[1],…,s[n-1]的全排列后接s[n];子问题2：生成n-1个元素s[1],…,s[n-2],s[n]的全排列后接s[n-1];………子问题n：生成n-1个元素s[2],…,s[n]的全排列后接s[1];-递归求解：子问题与原问题的性质相同，只不过规模为n-1。设原问题的求解算法为permute(s,n)，则子问题就是递归调用permute(s,n-1)。临界条件：一个元素的排列就是该元素本身。算法Permute(s[],n){//n个元素s[1..n],输出所有的排列ifn=1thenprint(s);//输出s的一个排列else{Permute(s,n-1);//第一个子问题求解，不需要交换s[n]fori←n-1downto1do{swap(s[i],s[n]);//交换s[i],s[n]，后接S[n-1]到S[1]Permute(s,n-1);swap(s[i],s[n]);//交换s[i],s[n],使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)最大子段和；直接算法：T(n)=O(n2)分治算法：T(n)=O(nlogn)动态规划算法：T(n)=O(n)b[j]表示所有下标以j结束的最大子段和如果b[j]是最大子段和，那么b[j-1]一定也是最大子段和。(4)最长公共子序列；12贪心算法(ch16)1.方法的基本思想和基本步骤基本思想：从问题的某一个初始解出发，通过一系列的贪心选择——当前状态下的局部最优选择，逐步逼近给定的目标，尽可能快地求得更好的解。其中贪心点的选取是关键的步骤。求解步骤：从问题的某一初始解出发；while依据贪心策略朝给定目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；2.贪心算法的正确性保证：满足贪心选择性质贪心算法的正确性，就是要证明按贪心准则求得的解是全局最优解。3.贪心算法与动态规划的比较(1)动态规划的每一次选择都依赖于子问题的解决，而贪心法会快速选择当前看起来解决问题最好的办法。(2)动态规划要先解决子问题，而贪心法可以在解决子问题之前做出选择。(3)动态规划是自底向上的，而贪心法是自顶向下的。(4)动态规划法通常教复杂，运行较慢，而贪心法较简单，运行较快。4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质两种背包问题都满足最优子结构性质，都可以用动态规划来求解；小数背包问题还具有贪心选择性质，用贪心法求解更简单、更快速。但0-1背包问题用贪心法求解不一定能得到最优解。5.算法设计(1)小数背包；按价值率（价值/重量）最大贪心，使单位重量价值增长最快。时间主要花在排序上。(2)活动安排；贪心策略设各活动已按结束时间排序：f1≤f2≤…≤fn，先选出活动1，然后按活动编号从小到大的次序依次选择与当前活动相容的活动。注：这种策略使剩余的可安排时间极大化，以便于安排尽可能多的相容活动。(3)找钱问题(略)；13回溯法(sch2)方法的基本思想和基本步骤基本思想：在问题的解空间中从根节点按照深度优先的方法搜索解空间树，在遇到死节点时果断跳过。基本步骤：定义问题的解空间（对问题的解进行编码）用树或图表示解空间的结构深度优先遍历解空间并果断跳过死节点的子树。2.回溯法是一种深度遍历的搜索3.术语:三种搜索空间,活结点,死结点,扩展结点,开始结点,终端结点三种搜索空间：-表序表示:搜索对象用线性表数据结构表示;-显式图表示:搜索对象在搜索前就用图(树)的数据结构表示;-隐式图表示:除了初始结点,其他结点在搜索过程中动态生成.缘于搜索空间大,难以全部存储.活节点：当前正在访问的节点扩展节点：指可以以该节点为出发点继续遍历的节点死节点：指在该节点处无法再纵深扩展的节点。开始节点：通常指解空间的根节点终端节点：解空间的叶节点两种解空间树和相应的算法框架=1\*GB3①子集树：如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开始的数列形成全排列，则直接输出即可。TSP问题；基本思想：利用排列生成问题的回溯算法Backtrack(2)，对x[]={1,2,…,n}的x[2..n]进行全排列，则(x[1],x[2]),(x[2],x[3]),…,(x[n],x[1])构成一个回路。在全排列算法的基础上，进行路径计算保存以及进行限界剪枝。cc+=a[x[i-1]][x[i]];表示把当前节点当成最短路径上的点。cc-=a[x[i-1]][x[i]];表示回溯后取消最短路径上的当前点，尝试其他可能。14分枝限界法(sch3)1.方法的基本思想和基本步骤基本思想：在解空间树中,以广度优先BFS或最佳优先方式搜索最优解,利用部分解的最优信息,裁剪那些不能得到最优解的子树以提高搜索效率。基本步骤：①定义解空间(对解编码);②确定解空间的树结构;③按BFS等方式搜索:a.每个活结点仅有一次机会变成扩展结点；b.由扩展结点生成一步可达的新结点；c.在新结点中,删除不可能导出最优解的结点；//限界策略d.将余下的新结点加入活动表(队列)中；e.从活动表中选择结点再扩展；//分支策略f.直至活动表为空；与回溯法的区别(1)求解目标不同，回溯发通常会求出满足约束条件的所有解而分支限界法却只要尽快找到满足条件的一个解(2)搜索方式不同，回溯法采用深度优先而分支限界法采用广度优先或最佳优先。(3)对节点的扩展方式不同,分支限界法任何节点只有一次机会成为扩展节点，活节点一旦成为扩展节点，则一次性产生其所有子节点。(4)存储空间不同，分支限界法通常需要大量的存储空间。3.活结点的两种扩展方式(1)先进先出队列（FIFO）:从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同；(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)gcd(a,b)及其表示成a,b线性组合方法gcd(a,b)=ax+by中最小的数Euclid’sAlg.的运行时间Euclid(a,b){ifb=0thenreturna;elsereturnEuclid(b,amodb);}注:-Euclid’sAlg.递归调用的次数为O(logb)-算法应用到二个β位整数上，算法耗费O(β)算术运算和O(β3)位运算3.线性模方程的求解方法对线性模方程ax≡b(modn)调用EXTENDED_EUCLID(a,n)得出(d,x’,y’)的值求出特征解x0=x’(b/d)(modn)求出全解xi=x0+i(n/d)(modn)其中0=<i<=d-1中国余数定理及其相应线性同余方程组的求解对形如：x≡a1(modn1)x≡a2(modn2)…x≡ak(modnk)的模方程组m1=n2*n3*..*nK(即缺少n1的连乘)m2=n1*n3*..*nkm3=n1*n2*n4..*nk……mk-1=n1*n2*n3..*nk-2*nK-1mk=n1*n2*n3..*nK-1c1=m1(m1-1modn1)c2=m2(m2-1modn2)……ck=mk(mk-1modnk)(3)x=c1a1+c2a2+……+ckak（modn1*n2*..*nk）5.RSA算法(略)6.简单素数测试算法和伪素数测试算法PseudoPrime(n){ifModularExponentiation(2,n-1,n)!≡1(modn)thenreturnComposite;elsereturnPrime;}即验证2^(n-1)=1(modn)是否满足，若满足则可能为素数，不满足一定为合数注:-该算法判断出合数总是正确的;-如果算法给出的结论是素数，仅在基2的伪素数情形出错。7.MR算法的改进措施和算法复杂性算法的复杂性设n为β-bit整数，算法需要O(sβ)算术运算、O(β3)位运算算法的误判率-Th31.38n为奇合数，则n的Witness数大于(n-1)/2-Th31.39MR算法的误判率不超过2-s16串匹配(ch32)1.朴素的串匹配算法及其时间复杂度NAÏVE-STRING-MATCHER(T,P)n←length[T]m←length[P]fors←0ton-mifP[1..m]=T[(s+1)..(s+m)] print“patternoccurswithshift”sSo,theworst-caserunningtimeisΘ((n-m+1)m)butaverage-caseisO(n+m),Alsoworkswellinpractice.2.Rabin-Karp串匹配算法及其时间复杂度Foreachhit,i.e.,foreachswheretsp(modq),verifycharacterbycharacterwhethersisavalidshiftoraspurioushitIntheworstcase,everyshiftisverifiedRunningtimecanbeshownasO((n-m+1)m)Average-caserunningtimeisO(n+m)3.有限自动机串匹配算法及其时间复杂度Input:TextstringT[1..n],δandmResult:AllvalidshiftsdisplayedFINITE-AUTOMATON-MATCHER(T,m,δ)n←length[T]q←0fori←1ton q←δ(q,T[i])ifq=m print“patternoccurswithshift”i-mStringmatchingisefficient:Θ(n)EachcharacterisexaminedexactlyonceConstanttimeforeachcharacterBut…timetocomputeδisO(m||)δHasO(m||)entries该有限自动机的建立时间为O(m||)=O(7*3)KMP串匹配算法及其时间复杂度aababaabaPqPkComparepatternagainstitself;longestprefixofPthatisalsoasuffixofP5isP3;soπ[5]=3q1234567pababacaΠ0012301ππ[q]=max{k|k<qandPkisasuffixofPq}KMPAlgorithm2parts:KMP-MATCHER,PREFIXRunningtimePREFIXtakesO(m)KMP-MATCHERtakesO(m+n)17随机算法(sch4)随机算法的定义定义：是一个概率图灵机.也就是在算法中引入随机因素,即通过随机数选择算法的下一步操作。随机算法的分类：LasVegas和MonteCarloLasVegas算法运行结束时总能给出正确的解，但其运行时间每次有所不同。MonteCarlo算法可能得到不正确的结果，但这种概率是小的且有界的。(1)QuickSort属于LasVegas类型；不同的划分会导致不同的运行时间