第二章算法分析基础优秀课件.ppt

《第二章算法分析基础优秀课件.ppt》由会员分享，可在线阅读，更多相关《第二章算法分析基础优秀课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章算法分析基础第1页，本讲稿共40页算法分析的任务:对设计出的每一个具体的算法,利用数学工具，讨论其复杂度。2.1 2.1 算法分析体系及计量算法分析体系及计量第2页，本讲稿共40页对算法的评价有两个大的方面：一.对算法的维护的方便性。二.算法在实现运行时占有的机器资源的多少,即算法的运行的时间和空间效率。2.1.1 2.1.1 算法分析的评价体系算法分析的评价体系第3页，本讲稿共40页 对对算算法法的的分分析析和和评评价价，一一般般应应考考虑虑正正确确性性、可可维维护护性、可读性、运算量及占用存储空间等性、可读性、运算量及占用存储空间等诸多因素。诸多因素。其中评价算法的三条主要其中评价算

2、法的三条主要标准标准是：是：(1)(1)算法实现所耗费的算法实现所耗费的时间时间；(2)(2)算法实现所所耗费的存储算法实现所所耗费的存储空间空间，其中，其中 主要考虑辅助存储空间；主要考虑辅助存储空间；(3)(3)算法应易于算法应易于理解理解，易于编码，易于调，易于编码，易于调 试等等。试等等。第4页，本讲稿共40页 1.1.和算法执行时间相关的因素和算法执行时间相关的因素：1）问题中数据存储的数据结构2）算法采用的数学模型 3）算法设计的策略4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度 2.1.2 2.1.2 算法的时间复杂性算法的

3、时间复杂性第5页，本讲稿共40页2 2算法效率的衡量方法算法效率的衡量方法 通常有两种通常有两种衡量算法效率衡量算法效率的方法的方法:1 1）事后统计法（有缺点，较少使用）事后统计法（有缺点，较少使用）2 2）事前分析估算法）事前分析估算法 算法的时间效率是问题规模的函数。算法的时间效率是问题规模的函数。假假如如,随随着着问问题题规规模模n n的的增增长长,算算法法执执行行时时间间的的增增长长率率和和f(n)f(n)的增长率相同的增长率相同,则可记作则可记作:T(n)=(f(n)T(n)=(f(n)称称T(n)T(n)为为算算法法的的渐渐近近时时间间复复杂杂度度(Asymptotic(Asym

4、ptotic Time Time Complexity),Complexity),简称简称时间复杂度时间复杂度。是数量级的符号。是数量级的符号。第6页，本讲稿共40页3 3时间复杂度估算时间复杂度估算 因为：算法=控制结构+原操作(固有数据类型的操作)所以：算法的执行时间=原操作的执行次数*原操作的执行时间 语句的频度语句的频度指的是该语句重复执行的次数。一个算法转换为算法后所耗费的时间,除了与所用的计算软、硬件环境有关外，主要取决于算法中指令重复执行的次数，即语句的频度相关。第7页，本讲稿共40页 一个算法中所所有有语语句句的的频频度度之之和和构成了该算法的运行时间。例如：for(j=1;j

5、=n;+j)for(k=1;k=n;+k)+x；语句“+x、k=n、+k”的频度是n2，语句“j=1、k=1”的频度是1，语句“j=n;+j”的频度是n。算法运行时间为：3*n2+2n+2。第8页，本讲稿共40页 经经常常从从算算法法中中选选取取一一种种对对于于所所研研究究的的问问题题来来说说是是基基本本(或或者者说说是是主主要要)的的原原操操作作,以以该该基基本本操操作作在在算算法法中中重重复复执执行行的的次次数数作作为为算算法法运运行行时时间间的的衡衡量量准准则则。这这个个原原操操作作,多多数数情情况况下下是是最深层次循环体内的语句中的原操作最深层次循环体内的语句中的原操作。例如：例如：f

6、or(i=1;i=n;+i)for(i=1;i=n;+i)for(j=1;j=n;+j)for(j=1;j=n;+j)ci,j=0;ci,j=0;for(k=0;k=n;+k)for(k=0;k=n;+k)ci,j=ci,j+ai,k*bk,j;ci,j=ci,j+ai,k*bk,j;该算法的基本操作是乘法操作,时间复杂度为n3 3。第9页，本讲稿共40页例:n2+n+1的时间复杂度?解:与n2的数量级相等(该表达式当n足够大时约等于n2),这个算法的时间复杂度算法的时间复杂度为：T(n)=O(n2)。数量级相等是这样定义的,设f(n)是一个关于正整数n 的函数,若存在一个常数C，使 则称f(

7、n)与g(n)是同数量级的函数。上节 下节第10页，本讲稿共40页算法(渐进渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：(1)称为常数级 (logn)称为对数级 (n)称为线性级 (nc c)称为多项式级 (cn)称此为指数级 (n!)称为阶乘级 上节 下节第11页，本讲稿共40页 以上时间复杂度级别是由低到高排列的,其随规模n的增长率，由图2-1可见一斑：图2-1 T(n)与规模n的函数关系第12页，本讲稿共40页原则上一个算法的时间复杂度,最好不要采用指数级和阶乘级的算法,而应尽可能选用多项式级或线性级等时间复杂度级别较小的算法。对于较复杂的算法，可将

8、它分隔成容易估算的几个部分，然后再利用“O的求和原则得到整个算法的时间复杂度。例：若算法的两个部分的时间复杂度分别为 T1(n)=O(f(n)和 T2(n)=O(g(n)，则总的时间复杂度为：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)。第13页，本讲稿共40页4 4问题时间复杂度的上界和下界问题时间复杂度的上界和下界略第14页，本讲稿共40页5.5.算法时间复杂度的最好情况和最坏情况算法时间复杂度的最好情况和最坏情况 我们要确定能反映出算法在各种情况下工作的数据集我们要确定能反映出算法在各种情况下工作的数据集,选取的数据要能够反映、代表各种计算情况下的估算选取的数据要能够

9、反映、代表各种计算情况下的估算,包包括括最好情况下最好情况下的时间复杂度的时间复杂度(Tmax)(Tmax)最坏情况下最坏情况下的时间复杂度的时间复杂度(Tmin)(Tmin)平均情况下平均情况下的时间复杂度的时间复杂度(Tavg)(Tavg)最有实际价值的最有实际价值的,是是最坏情况下最坏情况下的时间复杂性。的时间复杂性。第15页，本讲稿共40页算法的存储量包括：1)输入数据所占空间:取决于问题本身,与算法无关2)算法本身所占空间:相对固定3)辅助变量所占空间2.1.3 2.1.3 算法的空间复杂性算法的空间复杂性第16页，本讲稿共40页 研究算法的空间效率，只需要分析除输入和算法之外的额外

10、空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作,否则,它应当是规模的一个函数。算法的空间复杂度是指算法在执行过程中所占辅助存储空间的大小用S(n)表示。算法的空间复杂度S(n)也可表示为:S(n)=(g(n)表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。第17页，本讲稿共40页NP完全性问题:属于“计算复杂性”研究的课题。计算复杂性:就是用计算机求解问题的难易程度。度量标准：一.计算所需的步数或指令条数(这叫时间复杂度)。二.计算所需的存储单元数量(这叫空间复杂度)。上节 下节2.1.4NP2.1.4NP完全问题完全问题第18页，本讲稿共40

11、页问题的复杂性和算法的复杂性的区别：只就时间复杂性说，算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度。P类问题:就是所有复杂度为多项式时间的问题的集合(易解的问题类,否则为难解的问题)。例如:梵塔问题 推销员旅行问题等第19页，本讲稿共40页NP问题:至今没有找到多项式时间算法解的一类问题,可以在多项式时间内验证一个解是否正确的问题,亦称为易验证问题类。NP完全问题(NPC问题,C代表complete):从NP类的问题中分出复杂性最高的一个子类。如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=N

12、P成立!要么每个NP完全问题都存在多项式时间的算法（即通常所指的有效算法）；要么所有NP完全问题都不存在多项式时间的算法。第20页，本讲稿共40页 目前已知的NP完全问题就有2000多个,其中有许多是非常重要的问题,如:货郎问题、最大独立集问题、背包问题、装箱问题、等等。第21页，本讲稿共40页遇到这类问题时，通常从以下几个方面来考虑并寻求解决办法:1)特殊情形特殊方法 2)动态规划和分枝限界方法 3)概率分析 4)近似算法 5)启发式算法 上节 下节第22页，本讲稿共40页 一具体算法的时间复杂度和空间复杂度往往是不独立的，在算法设计中要在时间效率和空间效率之间折衷。2.2 2.2 算法分析

13、实例算法分析实例第23页，本讲稿共40页 1 1仅依赖于问题规模的时间复杂度仅依赖于问题规模的时间复杂度 有一类简单的问题，其操作具有普遍性，也就是说对所有的数据均等价地进行处理，这类算法的时间复杂度，很容易分析。2.2.1 2.2.1 非递归算法分析非递归算法分析第24页，本讲稿共40页【例1】交换i和j的内容。Temp=i；i=j；j=temp；以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复

14、杂度是(1)。上节 下节第25页，本讲稿共40页【例【例2 2】循环次数直接依赖规模循环次数直接依赖规模n n (1)x=0；=0；(2)for(k-1；=n；+)(3)x+；(4)for(i=1；=n；+)(5)for(j=1；j=n；+)(6)y+；T(n)=(n2 2)。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。上节 下节y+第26页，本讲稿共40页【例【例3 3】循环次数间接依赖规模循环次数间接依赖规模n n(1)x=1；(2)for(i=1；i=n；i+)(3)for(j=1；j=i；j+)(4)for(k=1；k=0 and

15、Aik)(2)while(i=0 and Aik)(3)i=i-1 (3)i=i-1；(4)return i (4)return i；第29页，本讲稿共40页 此此算法的频度算法的频度不仅与问题规模不仅与问题规模n n有关，还与输入实例中有关，还与输入实例中A A的各元素取值及的各元素取值及k k的取值有关：的取值有关：1.1.若若A A中没有与中没有与k k相等的元素，则语句相等的元素，则语句(2)(2)的频度的频度f(n)=nf(n)=n；这是最坏情况。这是最坏情况。2.2.若若A A的最后一个元素等于的最后一个元素等于k,k,则语句则语句(2)(2)的频度的频度f(n)f(n)是常数是常

16、数1;1;这是最好情况。这是最好情况。第30页，本讲稿共40页 在求平均情况时，一般地假设查找不同元素的概率P是相同的,则算法的平均复杂度为：若对于查找不同元素的概率P不相同时，其算法复杂度就只能做近似分析，或在构造更好的算法或存储结构后，做较准确的分析。上节 下节第31页，本讲稿共40页2.2.2 2.2.2 递归算法分析递归算法分析第32页，本讲稿共40页【例【例1 1】求N！构造算法中的两个步骤：1）N!=N*(N-1)！2）0!=1，1!=1。递归算法如下：以n=3为例,调用过程如下：fact(3)-fact(2)-fact(1)-fact(2)-fact(3)递 归 回 溯第33页，

17、本讲稿共40页迭代法迭代法介绍：用迭代方法估计递归算法的解,就是充分利用递归算法中的递归关系,通过一定的代数运算和数学分析的级数知识,得到问题的复杂度。递归方程具体就是利用递归算法中的递归关系写出递归方程,迭代地展开的右端，使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端即方程的解的估计。上节 下节第34页，本讲稿共40页【例【例1 1】求n!递归方程为：T(n)=T(n-1)+O(1)其中O(1)为一次乘法操作.迭代求解过程如下：T(n)=T(n-2)+O(1)+O(1)=T(n-3)+O(1)+O(1)+O(1)=O(1)+O(1)+O(1)+O(1)=n*O(1)=O(n)

18、第35页，本讲稿共40页【例【例2 2】抽象地考虑以下复杂一点的递归方程，且假设n=2k，则迭代求解过程如下：=O(n)第36页，本讲稿共40页一般地，当递归方程为：一般地，当递归方程为：T（n）=aT（n/c）+O(n)，T（n）的解为：）的解为：O(n)a1 时时 O(nlogcn)a=c且且c1时时 O(nlogca)ac且且c1时时第37页，本讲稿共40页 在满足正确性、可靠性、健壮性、可读性等质量因素的前下，设法提高算法的效率。看两组操作：(1)a=a+b；b=a-b；a=a-b；(2)t=a；a=b；b=t；2.2.3 2.2.3 提高算法质量提高算法质量两组操作的功能都是：“交换

19、变量a、b中的数据”。虽然第一组操作节省了一个存储空间，但失去了可读性，是不可取的。第38页，本讲稿共40页 下面给出一些原则上的建议：1.1.保证正确性、可靠性、健壮性、可读性保证正确性、可靠性、健壮性、可读性；1）当心那些视觉上不易分辨的操作符发生书写错误(与=)。2）算法中的变量(指针、数组)在当成右值使用（被引用）前，一定要有确切的含义，或是被赋值或是经模块接口 传递信息。3）算法中要当心变量发生上溢或下溢，数组的下标越界。4）写算法时就要考虑，可能出现错误的情况，提示执行错 误处理算法。5）编写算法时区别问题的循环条件和停止条件，不要误用。6）注意算法中循环体，或条件体的内容，不要误

20、把循环体 内的操作写互循环体外或者出现相反的错误。第39页，本讲稿共40页2 2提高效率提高效率。1）以提高算法的全局效率为主，提高局部效率为辅。2）在优化算法的效率时，应当先找出限制效率的“瓶颈”。3）多数情况下，时间效率和空间效率可能是对立的，此时 应当分析哪个更重要，作出适当的折衷。4）可以考虑先选取合适的数据结构，再优化算法。5）递归过程的实现决定了递归算法的效率往往很低，费 时和费内存空间。在解决问题时，如果能使用递推法 解决的，应考虑用递推法，其效率更高些。6）注意多用数学方法，可以大大提高算法效率。7）另外还有一些细节上的问题,如:乘、除运算的效率比 加、减法运算低。上节 下节第40页，本讲稿共40页