搜索
计算机算法设计与分析1.1算法的定义和特征1)什么是算法？算法是求解某一特定问题的一组有穷规则的集合，它是由若干条指令组成的有穷符号串。2）算法的五个重要特性确定性、可实现性、输入、输出、有穷性3）算法设计的质量指标正确性，可读性，健壮性，效率与存储量算法和程序的区别程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现任何一种程序设计语言都可以实现任何一个算法算法的有穷性意味着不是所有的计算机程序都是算法问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法一般只考虑三种情况下的时间性:最坏情况、最好情况和平均情况下的复杂性，分别记为Tmax(n)、Tmin(n)和Tavg(n)算法复杂性=算法所需要的计算机资源=时间复杂性+空间复杂性算法渐近复杂性定义1.2设算法的执行时间)(nT，如果存在)(*nT，使得0)()()(lim*nTnTnTn就称)(*nT为算法的渐近时间复杂性。1）上界函数定义1如果存在两个正常数c和n0，对于所有的n≥n0，有|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，对于所有的n≥n0，有|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，对于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|则记作含义：算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：既有f(n)=Ω(g(n))，又有f(n)=Ο(g(n))记号表明算法的运行时间有一个较准确的界))(()(ngnf3）“平均情况”限界函数最优算法问题的计算时间下界为(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数列。它可以递归地定义为：边界条件递归方程110)2()1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：intfibonacci(intn){if(n=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}分治算法总体思想分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。分治法的基本步骤（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为n／k的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：11)()/()1()(nnnfknkTOnT通过迭代法求得方程的解：nbnnnTklog)(二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。据此容易设计出二分搜索算法：templateclassTypeintBinarySearch(Typea[],constType&x,intl,intr){while(r=l){intm=(l+r)/2;if(x==a[m])returnm;if(xa[m])r=m-1;elsel=m+1;}return-1;}算法复杂度分析：每执行一次算法的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)渐进意义下的最优算法11)()2/(2)1()(nnnOnTOnT算法消去递归的合并排序算法输入：具有个元素的数组A[]输出：按递增顺序排序的数组A[]1.templateclassType2.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+sn)12.merge(A,i,i+s-1,n-1,n-i);13.}14.}合并排序算法mergeSort的递归过程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]快速排序privatestaticvoidqSort(intp,intr){if(pr){intq=partition(p,r);//以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，a[q+1:r]中任何元素大于等于a[q]。下标q在划分过程中确定。qSort(p,q-1);//对左半段排序qSort(q+1,r);//对右半段排序}}templateclassTypeintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]x&&ir);//将x的元素交换到左边区域while(a[--jx);//将x的元素交换到右边区域if(i=j)break;Swap(a[i],a[j]);;}a[p]=a[j];a[j]=x;returnj;}快速排序线性时间选择问题问题描述：给定线性集中n个元素和一个整数k,要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为我们要找的元素。当k=1时，即找最小元素；当k=n时，即找最大元素；当k=(n+1)/2时，称为找中位数。线性时间选择templateclassTypeTypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];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（1：j-1)中，再对之进一步划分。若k=j,则A(j)就是第k小元素若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){用某个简单排序算法对数组a[p:r]排序;returna[p+k-1];};for(inti=0;i=(r-p-4)/5;i++)将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+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)7575)4/3()5/()(21nnnTnTnCCnT32基本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一个子问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。动态规划算法动态规划算法的两个基本要素对于一个多阶段过程问题，最优决策是否存在，不仅依赖于该问题是否有最优子结构性质，而能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。34动态规划基本步骤找出最优解的性质，并刻划其