算法复杂度资料.pptx

文档介绍：计算复杂性理论和算法分析计算机科学导论第六讲计算机科学技术学院陈意云0551-63607043,******@://./~yiyun/课程内容课程内容围绕学科理论体系中的模型理论, 给定模型M,哪些问题可以由模型M解决;,如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、 给定模型M和一类问题,解决该类问题需多少资源本讲座用简单的例子来扼要介绍计算复杂性和算法分析2讲座提纲基本知识计算资源,可计算理论,计算复杂性理论,算法分析复杂性的计量问题规模、复杂性函数、最坏、最好和平均三种情况的时间复杂性复杂性的渐近行为及其阶复杂性的渐近行为、渐近意义下的记号O、记号O的运算规则、复杂性渐近阶分析的重要性算法复杂性渐近阶的分析算法的复杂性渐近阶的分析、语句规则的例举3基本知识计算资源在计算复杂性理论内,计算资源是指在某个计算模型之下,求解各种问题所要消耗的资源时间资源:求解问题所需花费的时间,通常用计算步数来度量空间资源:求解问题所需占用的空间,通常用存储器空间的大小来度量计算所需资源的多少是衡量计算复杂性的依据 实际应用关心的资源与理论上的有区别:硬件资源(如计算机、存储器)、软件资源、网络资源(如通信带宽)等4基本知识计算复杂性理论是理论计算机科学和数学的一个分支,它致力于将可计算问题根据其本身固有的难度进行分类,以及把这些类别相互联系起来它尝试把问题分成两类:在适当的资源限制下能解(容易)和不能解(困难)的问题。若求解需很多资源(无论什么算法),则被认为是难解的通过引入计算模型来研究这些问题,并定量计算解决问题所需的资源(时间和空间),由此把确定资源的方法数学化作用之一是确定计算机能解和不能解的实际界线5基本知识计算复杂性理论与可计算性理论和算法分析的区别和联系算法分析致力于分析求解一个问题的某具体算法所需的资源量,而计算复杂性理论关注的是用所有可能算法解决同一个问题层面上的一般性议题资源受限和不受限是区分计算复杂性理论和可计算性理论的一个重要标志:可计算性理论关注的是原则上可以用算法求解的问题(把问题区分为可解和不可解)6基本知识算法分析确定执行一个算法需要消耗的计算资源的数量的分析过程算法的效率或复杂度表示为一个函数,其定义域是输入数据的规模(长度,算法大都设计成允许任意长的输入),值域通常是执行步数(时间复杂度)或所需存储空间数量(空间复杂度)在算法的理论分析中,通常是估计算法渐近意义上的复杂度精确分析算法的效率有时也可行,但它通常基于一些与具体实现相关的假设7复杂性的计量两种查找算法的效率比较intsearch(intval){//顺序查找 intj=0; //inta[m]无重复且已按从小到大排序 while(a[j]<val&&j<m1){ j=j+1; } if(a[j]==val){ returnj; }else{ return1; }//在最坏情况下,需要把val与a的所有分量比较}8复杂性的计量两种查找算法的效率比较intsearch(intval){//二分查找inti,j,k; //inta[m]无重复且已按从小到大排序 i=0;j=m1; while(i<=j){ k=i+(ji)/2; if(val<=a[k])j=k1; if(val>=a[k])i=k+1; } if(ji==1){return1;}else{returnk;}} //在最坏情况下,只需要把val与a的log2m个 //分量比较,显然效率高于前一个算法9复杂性的计量两种求斐波那契数列前n+i(intn){//假定n>=0,递归算法inti; for(i=0;i<=n;i++)printf(“%d\n”,fib(n));}intfib(intk){if(k==0)return0;elseif(k==1)return1; elsereturnfib(k1)+fib(k2);}对该数列a0,a1,…,an,ak(0k<n)被重复计算多次10