计算机算法设计与分析总复习PPT课件

.,计算机算法设计与分析,.,1.1算法的定义和特征,1)什么是算法？算法是求解某一特定问题的一组有穷规则的集合，它是由若干条指令组成的有穷符号串。,2）算法的五个重要特性确定性、可实现性、输入、输出、有穷性,3）算法设计的质量指标正确性，可读性，健壮性，效率与存储量,.,算法和程序的区别,程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现任何一种程序设计语言都可以实现任何一个算法算法的有穷性意味着不是所有的计算机程序都是算法,.,问题求解(ProblemSolving),理解问题,精确解或近似解选择数据结构算法设计策略,设计算法,.,一般只考虑三种情况下的时间性:最坏情况、最好情况和平均情况下的复杂性，分别记为Tmax(n)、Tmin(n)和Tavg(n),算法复杂性=算法所需要的计算机资源=时间复杂性+空间复杂性,.,算法渐近复杂性,.,1）上界函数,定义1如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。f(n)的数量级就是g(n)。f(n)的增长最多像g(n)的增长那样快试图求出最小的g(n)，使得f(n)=(g(n)。,.,.,算法分类（计算时间）,多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法：计算时间用指数函数限界的算法。常见的指数时间限界函数：(2n)(n！)(nn)说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。,.,典型的计算时间函数曲线,.,定义1.2如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。f(n)的增长至少像g(n)的增长那样快试图求出“最大”的g(n)，使得f(n)=(g(n)。,2）下界函数,.,定义1.3如果存在正常数c1，c2和n0，对于所有的nn0，有c1|g(n)|f(n)|c2|g(n)|则记作含义：算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：既有f(n)=(g(n)，又有f(n)=(g(n)记号表明算法的运行时间有一个较准确的界,3）“平均情况”限界函数,.,最优算法,问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。,.,第2章递归与分治策略,.,2.1递归的概念,直接或间接地调用自身的算法称为递归算法。函数自身给出定义的函数称为递归函数。基于归纳法的递归基于分治法的递归,.,2.1递归的概念,例Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下：intfibonacci(intn)if(n=1)return1;returnfibonacci(n-1)+fibonacci(n-2);,.,分治算法总体思想,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。,.,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,.,分治法的基本步骤（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。,.,分治法的复杂性分析,一个分治法将规模为n的问题分成k个规模为nk的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,.,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法：templateintBinarySearch(Typea,constType,算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。,.,合并排序,基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,publicstaticvoidmergeSort(Comparablea,intleft,intright)if(leftright)/至少有2个元素inti=(left+right)/2;/取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组bcopy(a,b,left,right);/复制回数组a,复杂度分析T(n)=O(nlogn)渐进意义下的最优算法,.,算法消去递归的合并排序算法输入：具有个元素的数组A输出：按递增顺序排序的数组A1.template2.voidmerge_sort(TypeA,intn)3.4.inti,s,t=1;5.while(tn)6.s=t;t=2*s;i=0;7.while(i+tn)8.merge(A,i,i+s-1,i+t-1,t);9.i=i+t;10.11.if(i+s=j)break;Swap(ai,aj);ap=aj;aj=x;returnj;,快速排序,.,线性时间选择问题,问题描述：给定线性集中n个元素和一个整数k,要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为我们要找的元素。当k=1时，即找最小元素；当k=n时，即找最大元素；当k=(n+1)/2时，称为找中位数。,.,线性时间选择,templateTypeRandomizedSelect(Typea,intp,intr,intk)if(p=r)returnap;inti=RandomizedPartition(a,p,r),j=i-p+1;if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);,.,线性时间选择问题算法,上述Partition算法可用来求选择问题的有效解。如果划分元素v测定在A（j）的位置上，则有j-1个元素小于或等于A(j),且有n-j个元素大于或等于A(j)。因此，若kj,则第k小元素在A（j+1:n)中，再对之进一步划分。,在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。,.,将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。,线性时间选择,.,TypeSelect(Typea,intp,intr,intk)if(r-p75)用某个简单排序算法对数组ap:r排序;returnap+k-1;for(inti=0;i=(r-p-4)/5;i+)将ap+5*i至ap+5*i+4的第3小元素与ap+i交换位置;/找中位数的中位数，r-p-4即上面所说的n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);,复杂度分析T(n)=O(n),.,32,基本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一个子问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。,动态规划算法,.,动态规划算法的两个基本要素对于一个多阶段过程问题，最优决策是否存在，不仅依赖于该问题是否有最优子结构性质，而能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。,.,34,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,.,35,矩阵连乘问题,穷举法动态规划,将矩阵连乘积简记为Ai:j，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量,.,建立递归关系,令mij,1i,jn，为计算Ai,j的最少数乘次数，则原问题为m1n。当i=j时，Ai,j为单一矩阵，mij=0；当ij时，利用最优子结构性质有：,mij=,minmik+mk+1j+pi1pkpjikj,其中矩阵Ai，1in，的维数为pi1pi。,根据此递归式就可以直接用递归程序来实现。,.,消除重复的矩阵连乘算法,VoidMatrixChain(intp,intn,int*m,int*s)for(inti=1;i=n;i+)mii=0;/将对角线元素赋值为零，即单个矩阵计算量为0for(intr=2;r=n;r+)for(inti=1;i=nr+1;i+)intj=i+r1;(5)mij=mi+1j+pi1*pi*pj;/计算Ai,j=Ai:iAi+1:jsij=i;/记下断点i(7)for(intk=i+1;kj;k+)intt=mik+mk+1j+pi1*pk*pj;/对ikj,逐个计算Ai,j=Ai:kAk+1:jif(tmij)mij=t;sij=k;/记下较小的mij及相应的断点k,.,.,39,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，和当i=0或j=0时，空序列是A和B的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,.,40,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,voidLCSLength(intm，intn，char*x，char*y，int*c，int*b)inti，j;for(i=1;i=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;,构造最长公共子序列voidLCS(inti，intj，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);cout0,vi0，(x1,x2,xn)为最优解。,.,55,首先计算每种物品单位重量的价值vi/wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高(即vi/wi尽可大的)的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。若最后一个物品不能全部装入时，仅装其一部分使背包装满即可。具体算法可描述如下页：,用贪心算法解背包问题的基本思想：,.,贪心解背包问题,首先计算每种物品单位重量的价值vi/wi，然后，将尽可能多的单位重量价值最高的物品装入背包。voidKnapsack(intn,floatM,floatv,floatw,floatx)Sort(n,v,w);/将各种物品按单位重量价值排序inti;for(i=1;i=n;i+)xi=0;/将解向量初始化为零floatc=M;/是背包剩余容量初始化为Mfor(i=1;in)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i当前最优载重量bestw,1,0,1,1,1,1,0,0,0,不满足约束函数,1,不满足上界函数,0,0,1,.,装载问题算法描述,n集装箱数；w集装箱重量数组；c第一艘轮船载重量；cw在遍历结点处的当前载重量bsetw当前最优载重量,privatestaticvoidbacktrack(inti)/搜索第i层结点if(in)/到达叶结点if(cwbestw)bestw=cw;return;if(cw+win)/到达叶结点更新最优解bestx,bestw;return;r-=wi;if(cw+wibestw)/搜索右子树xi=0;backtrack(i+1);r+=wi;,复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O(2n)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n2n)。进一步改进算法，可降低时间复杂性为O(2n)。,.,N-皇后问题定义,4皇后问题：,8皇后问题：,.,经典的回溯算法，该算法的思路如下：依次在棋盘的每一行上摆放一个皇后。每次摆放都要检查当前摆放是否可行。如果当前的摆放引发冲突，则把当前皇后摆放到当前行的下一列上，并重新检查冲突。如果当前皇后在当前行的每一列上都不可摆放，则回溯到上一个皇后并且将其摆放到下一列上，并重新检查冲突。如果所有皇后都被摆放成功，则表明成功找到一个解，记录下该解并且回溯到上一个皇后。,.,求解N后问题中的数据表示,i-j=k-l,i+j=k+l,.,问题分析,解向量：(x1,x2,xn)，xi表示皇后i放在棋盘的第i行的第xi列。显约束：xi=1,2,n隐约束：1)不同列：xixj(ij)2)不处于同一正、反对角线：|i-j|xi-xj|解空间：排列树约束函数：xixj(ij)and|i-j|xi-xj|,.,算法描述,/place函数测试若将皇后k放在xk列是否与前面已放置的k-1个皇后都不在同一列，而且都不在同一斜线上。boolQueen:Place(intk)for(intj=