0.算法概论

计算机算法设计与分析赵建军黄正东算法设计与分析目录第一章算法及计算几何概述第三章凸壳及其算法第八章动态规划第九章贪心算法第十章回朔法第十一章分支限界法第七章递归与分治第六章NP完全性理论简介第二章多边形与几何体定位第四章Voronoi图及其应用第五章交与并3参考教材•王晓东《算法设计与分析》，清华大学出版社，2003•周培德《计算几何－算法分析与设计》清华大学出版社，2000算法概述AlgorithmIntroduction第一章介绍算法设计的基本概念及算法分析的方法和准则.算法设计与分析5一系列将问题的输入转换为输出的计算或操作步骤。算法设计与分析算法概述1.1算法Algorithm2).确定性definiteness算法的每个步骤必须有明确的意义,对每种可能的情况,算法都要给出确定的操作.1).有穷性finiteness算法必须在执行有穷步后终止,且每一步均在有限时间内完成3).能行性effectiveness算法中的每个步骤是能够实现的,算法执行结果要达到预期目的3.计算机算法的一般特征4).有0个或多个输入项,至少有一个输出项.1问题问题是一组需要完成的任务，数学上可将问题看作函数2算法6算法设计与分析算法概述数值型算法:算法中的基本运算为算术运算.非数值型算法:算法中的基本运算为逻辑运算.串行算法:串行计算机上执行的算法.并行算法:并行计算机上执行的算法.从处理方式上6.算法分类从解法上5.算法描述语言1).数据:运算序列中作为运算对象和结果的数据.2).运算:运算序列中的各种运算:赋值,算术和逻辑运算3).控制和转移:运算序列中的控制和转移.4.算法的三个要素自然语言,数学语言,流程图,程序设计语言等等.7算法设计与分析算法概述7.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言,对所求解的问题做准确的描述.通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法.证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序.8算法设计与分析算法概述1.2算法复杂性分析1.复杂性的计量k1I)(N,etiii显然,它与问题的规模,算法的输入数据及算法本身有关.将时间复杂性和空间复杂性分别考虑,并用T和S表示.则T=T(N,I,A)S=S(N,I,A)将A隐含在函数名中,则T=T(N,I,A)简化为T=T(N,I)算法的复杂性:算法执行所需的时间和空间的数量.令N:问题的规模I:输入数据A:算法本身则算法的复杂性C=F(N,I,A)设一台抽象计算机提供的元运算有k种,分别记作O1,…,Ok设这些元运算每执行一次所需时间分别为t1,t2,…,tk,设算法A中用到Oi的次数为ei,i=1,…,k,则ei=ei(N,I)T=T(N,I)=9算法设计与分析算法概述算法的复杂性最好情况:Tmin(N)=T(N,I)===最坏情况:Tmax(N)=T(N,I)===平均情况:Tavg(N)==kiiiINet1)(,kiiiINet1)(,kiiiINet1)(~,)(INT~,NDIminkiiiINet1)(,NDImaxkiiiINet1)(*,NDIIPI)T(N,)()(*,INTnDIIP)(NDIminNDImaxI~I~例题1-1其中DN:规模为N的所有合法输入的集合I*:DN中达到Tmax(N)的一个输入:DN中达到Tmin(N)的一个输入P(I):出现输入为I的概率算法设计与分析已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.functionsearch(c){i:=1;awhileA[i]candimdo2mti:=i+1;(m-1)(s+a)ifA[i]=ctthensearch:=i;elsesearch:=0;a}算法1-1:顺序查找例题1-1分析:问题的规模为m,设元运算执行时间为赋值:a,判断:t,加法:s,并设c在A中.最好情况Tmin(m)=2a+3t最坏情况Tmax(m)=(m+1)a+(2m+1)t+(m-1)s平均情况Tavg(m)=0.5(m+3)a+(m+2)t+0.5(m-1)s算法设计与分析算法1-2:二分查找(假定c是A的最后一元)例题1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b.最坏情况Tmax(m)=6a+4t+2s+d+(2a+2s+3t+d)logmfunctionb-search(c){L:=1;U:=m;2afound:=false;awhilenotfoundandU=Ldot(logm+2){i:=(L+U)div2;(a+s+d)(logm+1)ifc=A[i]t(logm+1)thenfound:=trueaelseifcA[i]t(logm+1)thenL:=i+1(s+a)(logm+1)elseU:=i-1}iffoundthenb-search:=ielseb-search:=0a}12算法设计与分析算法概述算法的复杂性2复杂性的渐进性态1).渐进性态)(Tn~)(nT~)(nT~)(nT~)(nT~)(nT~)(Tn~)(Tn~设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在一个函数使得当n,有(T(n)-)/T(n)0称是T(n)当n时的渐进性态或渐进复杂性.在数学上,T(n)与有相同的最高阶项.可取为略去T(n)的低阶项后剩余的主项.当n充分大时我们用代替T(n)作为算法复杂性的度量,从而简化分析.例如T(n)=3n2+4nlogn+7,则可以是3n2.若进一步假定算法中所有不同元运算的单位执行时间相同,则可不考虑所包含的系数或常数因子。渐进分析适用于n充分大的情况,当问题的规模很小时,或比较的两算法同阶时,则不能做这种简化.13算法设计与分析算法概述算法的复杂性2).渐进性态的阶又如算法1-1中Tmin(m)=2a+3t,Tmax(m)=(m+1)a+(2m+1)t+(m-1)s,Tmin(m)=O(1)Tmax(m)=O(m)例如3n=O(n),n+1024=O(n),n2=O(n3)?n3=O(n2)?2n2+11n-10=O(n2)若存在正常数c和自然数N0使得当NN0时,有f(N)cg(N)则称函数f(N)在N充分大时有上界,且g(N)是它的一个上界,记为f(N)=O(g(N)),也称f(N)的阶不高于g(N)的阶.设f(N)和g(N)是定义在正整数集上的正函数,(1)大O表示法(算法运行时间的上限)14算法设计与分析算法概述算法的复杂性例如估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶.分析:内循环体只需O(1)时间,故fori:=1tondoforj:=1toido{s1,s2,s3,s4};s1,s2,s3,s4为单一赋值语句ij1O(1))O()1O(1iij外循环共需)O(N)21O()O()O(21N1)(NNiiNii1.O(f)+O(g)=O(max(f,g))2.O(f)+O(g)=O(f+g)3.O(f)·O(g)=O(f·g)4.如果g(n)=O(f(n)),则O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n))=O(f(n))运算法则内循环共需15算法设计与分析算法概述算法的复杂性(2)大表示法(算法运行时间的下限）f(N)=(g(N))当且仅当f(N)=O(g(N))且f(N)=(g(N))称函数f(N)与g(N)同阶.算法的渐进复杂性的阶对于算法的效率有着决定性的意义:多项式阶算法(有效算法):时间复杂性与规模N的幂同阶.指数阶算法:时间复杂性与规模N的一个指数函数同阶.最优算法:时间复杂性达到其下界的算法.如果正常数c和自然数N0使得当NN0时,有f(N)cg(N)则称函数f(N)在N充分大时有下限,且g(N)是它的一个下限,记为f(N)=(g(N))也称f(N)的阶不低于g(N)的阶。(3)表示法16算法设计与分析算法概述算法的复杂性图1时间函数的增长率常见的多项式阶有:O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)常见的指数阶有:对规模较小的问题,决定算法工作效率的可能是算法的简单性而不是算法执行的时间.当比较两个算法的效率时,若两个算法是同阶的,必须进一步考察阶的常数因子才能辨别优劣.17算法设计与分析算法概述算法的复杂性3.渐进分析时间复杂性渐进阶分析的规则:(最坏情况)1).赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间2).执行条件语句ifcthenS1elseS2的时间为TC+max(TS1,TS2).3).选择语句caseAofa1:s1；a2:s2；...；am:sm需要的时间为max（TS1,TS2,...,TSm）.4).访问数组的单个分量或纪录的单个域需要一个单位时间.5).执行for循环语句的时间=执行循环体时间*循环次数.6).whilecdos(repeatsuntilc)语句时间=(Tc+Ts)*循环次数.7).用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间8).过程或函数调用语句对非递归调用,根据调用层次由里向外用规则1-7进行分析；对递归调用,可建立关于T(n)的递归方程,求解该方程得到T(n).例题1-1算法设计与分析算法1-2:二分查找(假定c是A的最后一元)例题1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b.最坏情况Tmax(m)=6a+4t+2s+d+(2a+2s+3t+d)logmfunctionb-search(c){L:=1;U:=m;2found:=false;1whilenotfoundandU=Ldo3{i:=(L+U)div2;3ifc=A[i]1thenfound:=true1elseifcA[i]1thenL:=i+11elseU:=i-1}iffoundthenb-search:=ielseb-search:=01}Logm+1算法设计与分析已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.例题1-1functionb-search(c,L,U){ifULthen1b-search:=01else{index:=(L+U)div2;3element:=A[index];2ifelement=cthen1b-search:=index;elseifelementcthen1b-search:=b-search(c,L,index-1);3+T(m/2)elseb-search:=b-search(c,index+1,U);3+T(m/2)};}设T(m)是b-search在最坏情况下的时间复杂性,则T(m)满足如下递归方程:2m=013m=111+T(m/2)m1T(m)=解得:T(m)=11·logm+13=(logm)算法1-3:二分查找递归算法算法设计与分析求Fibonacci数列的前N项a0,a1,…aN其中,a0=0,a1=1,ai=ai-1+ai-2算法1-4Procedureseq(n)functionA(n){ifn=0then1A:=01elseifn=1then1A:=11elseA:=A(n-1)+A(n-2)6+F(n-1)+F(n-2)};{ifn0then1errorelsefori:=0tondowriteln(A(i))(