计算复杂性和算法分析计算机科学导论第六讲（陈意云）

《计算复杂性和算法分析计算机科学导论第六讲（陈意云）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算复杂性和算法分析计算机科学导论第六讲计算机科学技术学院陈意云课程内容课程内容围绕学科理论体系中的模型理论,程序理论和计算理论1.模型理论关心的问题给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力2.程序理论关心的问题给定模型M，如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3.计算理论关心的问题给定模型M和一类问题,解决该类问题需多少资源本讲座用简单的例子来扼要介绍计算复杂性和算法分析2讲座提纲基本知识可计算理论,计算资源,计算复杂

2、性理论,算法分析复杂性的计量问题规模、复杂性函数、最坏、最好和平均三种情况的时间复杂性复杂性的渐近行为及其阶复杂性的渐近行为、渐近意义下的记号O、记号O的运算规则、复杂性渐近阶分析的重要性算法复杂性渐近阶的分析算法的复杂性渐近阶的分析、语句规则的例举3基本知识可计算理论研究计算的一般性质的数学理论，也称算法理论通过建立计算的数学模型,区分可计算与不可计算可计算函数：能够在抽象计算机上编出程序计算其值的函数。这样的程序称为算法这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的可计算性：指一个实际问题

3、是否可以使用计算机来解决（能解决一定是指有限步内解决）上一讲介绍的就是计算模型和可计算函数4基本知识计算资源在计算复杂性理论内，计算资源是指在某个计算模型之下，求解一个问题所要消耗的资源时间资源：求解问题所需花费的时间，通常用计算步数来度量空间资源：求解问题所需占用的空间，通常用存储器空间的大小来度量计算所需资源的多少是衡量计算复杂性的依据实际应用关心的资源与理论上的有区别：硬件资源（如计算机、存储器）、软件资源、网络资源（如通信带宽）等5基本知识计算复杂性理论是理论计算机科学和数学的一个分支，它致力

4、于将可计算问题根据其本身固有的难度进行分类，以及把这些类别相互联系起来它尝试把问题分成两类：在适当的资源限制下能解(容易)和不能解(困难)的问题。一个问题，若求解需很多资源(无论什么算法),则被认为是难解的通过引入计算模型来研究这些问题，并给出定量计算解决问题所需的资源(时间和空间)的方法，由此把确定资源的方法数学化作用之一是确定计算机能解和不能解的实际界线6基本知识计算复杂性理论研究问题之一：NP=?PP(Polynomial)：在确定型图灵机上有多项式时间算法的问题的集合NP(Nondetermi

5、nisticPolynomial)：在非确定型图灵机上有多项式时间算法的问题的集合NP=?P：是计算机科学中非常重要而又经历了几十年始终未解决的一个问题它的解决可导致一系列理论问题的解决7基本知识算法分析确定执行一个算法需要消耗的计算资源的数量的分析过程算法的效率或复杂度表示为一个函数，其定义域是输入数据的规模（长度，算法大都设计成允许任意长的输入），值域通常是执行步数（时间复杂度）或所需存储空间数量（空间复杂度）在算法的理论分析中，通常是估计算法渐近意义上的复杂度精确分析算法的复杂度有时也可行，但它

6、通常基于一些与具体实现相关的假设8基本知识可计算性、计算复杂性和算法分析的区别算法分析致力于分析求解一个问题的某个具体算法所需的资源量计算复杂性理论关注的是用所有可能算法解决同一类问题层面上的一般性议题可计算性理论关注的是原则上可以用算法求解的问题（把问题区分为可计算和不可计算）资源受限和不受限是区分计算复杂性理论和可计算性理论的一个重要标志9复杂性的计量两种查找算法的效率比较intsearch(intval){//顺序查找intj=0;//inta[m]无重复且已按从小到大排序while(a[j]<

7、val&&j=a[k])i=k+1;}if(ji==1){return1;}els

8、e{returnk;}}//在最坏情况下，只需要把val与a的log2m个//分量比较，显然效率高于前一个算法11复杂性的计量两种求斐波那契数列前n+1项算法的效率比较voidFibonacci(intn){//假定n>=0，递归算法inti;for(i=0;i<=n;i++)printf(“%d”,fib(n));}intfib(intk){if(k==0)return0;elseif(k==1)return1;elsereturnfib(k1)