《第二章-算法分析基础优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第二章-算法分析基础优秀PPT.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析的任务算法分析的任务:对对设设计计出出的的每每一一个个具具体体的的算算法法,利利用用数数学学工工具具，探探讨讨其其困难度。困难度。2.1 2.1 算法分析体系及计量算法分析体系及计量对算法的评价有两个大的方面：一.对算法的维护的便利性。二.算法在实现运行时占有的机器资源的多少,即算法的运行的时间和空间效率。2.1.1 2.1.1 算法分析的评价体系算法分析的评价体系 对对算算法法的的分分析析和和评评价价，一一般般应应考考虑虑正正确确性性、可可维维护护性性、可可读读性性、运运算算量量及及占占用用存存储储空空间间等等诸诸多因素。多因素。其中评价算法的三条主要标准是：其中评价算法的三条主要标
2、准是：(1)(1)算法实现所耗费的时间；算法实现所耗费的时间；(2)(2)算法实现所所耗费的存储空间，其中算法实现所所耗费的存储空间，其中 主要考虑协助存储空间；主要考虑协助存储空间；(3)(3)算法应易于理解，易于编码，易于调算法应易于理解，易于编码，易于调 试等等。试等等。1.和算法执行时间相关的因素：1）问题中数据存储的数据结构2）算法接受的数学模型 3）算法设计的策略4）问题的规模 5）实 现 算 法 的 程 序 设 计 语 言 6）编 译 算 法 产 生 的 机 器 代 码 的 质 量 7）计算机执行指令的速度 2.1.2 2.1.2 算法的时间困难性算法的时间困难性2 2算法效率的
3、衡量方法算法效率的衡量方法 通常有两种衡量算法效率的方法通常有两种衡量算法效率的方法:1 1）事后统计法（有缺点，较少运用）事后统计法（有缺点，较少运用）2 2）事前分析估算法）事前分析估算法 算法的时间效率是问题规模的函数。算法的时间效率是问题规模的函数。假假如如,随随着着问问题题规规模模n n的的增增长长,算算法法执执行行时时间间的的增增长长率率和和f(n)f(n)的的增增长长率率相相同同,则则可可记记作作:T(n)=(f(n):T(n)=(f(n)称称 T(n)T(n)为为 算算 法法 的的 渐渐 近近 时时 间间 困困 难难 度度(Asymptotic(Asymptotic Time
4、Time Complexity),Complexity),简简称称时时间困难度。间困难度。是数量级的符号。是数量级的符号。3 3时间困难度估算时间困难度估算 因为：因为：算算法法=限限制制结结构构+原原操操作作(固固有有数数据据类型的操作类型的操作)所以：所以：算算法法的的执执行行时时间间=原原操操作作的的执执行行次次数数*原操作的执行时间原操作的执行时间 语语句句的的频频度度指指的的是是该该语语句句重重复复执执行行的次数。的次数。一一个个算算法法转转换换为为算算法法后后所所耗耗费费的的时时间间,除除了了与与所所用用的的计计算算软软、硬硬件件环环境境有有关关外外，主主要要取取决决于于算算法法中
5、中指指令令重重复复执执行行的的次次数数，即语句的频度相关。即语句的频度相关。一个算法中全部语句的频度之和构成了该算法的运行时间。例如：for(j=1;j=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。常常常常从从算算法法中中选选取取一一种种对对于于所所探探讨讨的的问问题题来来说说是是基基本本(或或者者说说是是主主要要)的的原原操操作作,以以该该基基本本操操作作在在算算法法中中重重复复执执行行的的次次数数作作为为算算法法运运行行时时间间的的衡衡量量准准则则
6、。这这个个原原操操作作,多多数数状状况况下下是是最深层次循环体内的语句中的原操作。最深层次循环体内的语句中的原操作。例如：例如：for(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。例:n2+n+1的时间困难度?解:与n2的数量级相等(该表达式当n足够大时约等于n2),这个算法的时间困难度为：T(n)=O(n2)。数量
7、级相等是这样定义的,设f(n)是一个关于正整数n 的函数,若存在一个常数C，使 则称f(n)与g(n)是同数量级的函数。上节 下节算法(渐进)时间困难度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：(1)称为常数级 (logn)称为对数级 (n)称为线性级 (nc)称为多项式级 (cn)称此为指数级 (n!)称为阶乘级 上节 下节 以上时间困难度级别是由低到高排列的,其随规模n的增长率，由图2-1可见一斑：图2-1 T(n)与规模n的函数关系原则上一个算法的时间困难度,最好不要接受指数级和阶乘级的算法,而应尽可能选用多项式级或线性级等时间困难度级别较小的算法。对于较困难的算
8、法，可将它分隔成简洁估算的几个部分，然后再利用“O的求和原则得到整个算法的时间困难度。例：若算法的两个部分的时间困难度分别为 T1(n)=O(f(n)和 T2(n)=O(g(n)，则总的时间困难度为：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)。4 4问题时间困难度的上界和下界问题时间困难度的上界和下界略略5.5.算法时间困难度的最好状况和最坏状况算法时间困难度的最好状况和最坏状况 我们要确定能反映出算法在各种状况下工作我们要确定能反映出算法在各种状况下工作的数据集的数据集,选取的数据要能够反映、代表各种计选取的数据要能够反映、代表各种计算状况下的估算算状况下的估算,包括包
9、括最好状况下的时间困难度最好状况下的时间困难度(Tmax)(Tmax)最坏状况下的时间困难度最坏状况下的时间困难度(Tmin)(Tmin)平均状况下的时间困难度平均状况下的时间困难度(Tavg)(Tavg)最有实际价值的最有实际价值的,是最坏状况下的时间困难性。是最坏状况下的时间困难性。算法的存储量包括：1)输入数据所占空间:取决于问题本身,与算法无关2)算法本身所占空间:相对固定3)协助变量所占空间2.1.3 2.1.3 算法的空间困难性算法的空间困难性 探讨算法的空间效率，只须要分析除输入和算法之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作,否则,它应当是规
10、模的一个函数。算法的空间困难度是指算法在执行过程中所占协助存储空间的大小用S(n)表示。算法的空间困难度S(n)也可表示为:S(n)=(g(n)表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。NPNP完全性问题完全性问题:属于属于“计算困难性计算困难性”探讨的课题。探讨的课题。计算困难性计算困难性:就是用计算机求解问题的难易程度。就是用计算机求解问题的难易程度。度量标准：度量标准：一一.计算所需的步数或指令条数计算所需的步数或指令条数(这叫时间困难度这叫时间困难度)。二二.计算所需的存储单元数量计算所需的存储单元数量(这叫空间困难度这叫空间困难度)。上节上节下节下节
11、2.1.4NP2.1.4NP完全问题完全问题问题的困难性和算法的困难性的区分：只就时间困难性说，算法的困难性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的困难性是指这个问题本身的困难程度。P类问题:就是全部困难度为多项式时间的问题的集合(易解的问题类,否则犯难解的问题)。例如:梵塔问题 推销员旅行问题等NP问题:至今没有找到多项式时间算法解的一类问题,可以在多项式时间内验证一个解是否正确的问题,亦称为易验证问题类。NP完全问题(NPC问题,C代表complete):从NP类的问题中分出困难性最高的一个子类。假如一个NPC问题存在多项式时间的算法，则全部的NP问题都可以在多项式时
12、间内求解，即P=NP成立!要么每个NP完全问题都存在多项式时间的算法（即通常所指的有效算法）；要么全部NP完全问题都不存在多项式时间的算法。目前已知的NP完全问题就有2000多个,其中有很多是特别重要的问题,如:货郎问题、最大独立集问题、背包问题、装箱问题、等等。遇到这类问题时，通常从以下几个方面来考虑并寻求解决方法:1)特殊情形特殊方法 2)动态规划和分枝限界方法 3)概率分析 4)近似算法 5)启发式算法 上节 下节 一具体算法的时间困难度和空间困难一具体算法的时间困难度和空间困难度往往是不独立的，在算法设计中要在度往往是不独立的，在算法设计中要在时间效率和空间效率之间折衷。时间效率和空间
13、效率之间折衷。2.2 2.2 算法分析实例算法分析实例 1 1仅依靠于问题规模的时间困难度仅依靠于问题规模的时间困难度 有一类简洁的问题，其操作具有普遍有一类简洁的问题，其操作具有普遍性，也就是说对全部的数据均等价地性，也就是说对全部的数据均等价地进行处理，这类算法的时间困难度，进行处理，这类算法的时间困难度，很简洁分析。很简洁分析。2.2.1 2.2.1 非递归算法分析非递归算法分析【例1】交换i和j的内容。Temp=i；i=j；j=temp；以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间困难度为常数阶，记作T(n)=(1)。假如算法的执行时间不随着
14、问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间困难度是(1)。上节下节【例【例2 2】循环次数干脆依靠规模】循环次数干脆依靠规模n n(1)x=0(1)x=0；=0=0；(2)for(k-1(2)for(k-1；=n=n；+)+)(3)x+(3)x+；(4)for(i=1(4)for(i=1；=n=n；+)+)(5)for(j=1(5)for(j=1；j=nj=n；+)+)(6)y+(6)y+；T(n)=(n2)T(n)=(n2)。当有若干个循环语句时，算法的当有若干个循环语句时，算法的时间困难度是由嵌套层数最多的循环时间困难度是由嵌套层数最多
15、的循环语句中最内层语句的频度语句中最内层语句的频度f(n)f(n)确定的。确定的。上节上节下下节节y+【例【例3 3】循环次数间接依靠规模】循环次数间接依靠规模n n(1)x=1(1)x=1；(2)for(i=1(2)for(i=1；i=ni=n；i+)i+)(3)for(j=1(3)for(j=1；j=ij=i；j+)j+)(4)for(k=1(4)for(k=1；k=jk=0 and Aik)(2)while(i=0 and Aik)(3)i=i-1 (3)i=i-1；(4)return i (4)return i；此算法的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及k的取值有
16、关：1.若A中没有与k相等的元素，则语句(2)的频度f(n)=n；这是最坏状况。2.若A的最终一个元素等于k,则语句(2)的频度f(n)是常数1;这是最好状况。在求平均状况时，一般地假设查找不同元素的概率P是相同的,则算法的平均困难度为：若对于查找不同元素的概率P不相同时，其算法困难度就只能做近似分析，或在构造更好的算法或存储结构后，做较精确的分析。上节 下节2.2.2 2.2.2 递归算法分析递归算法分析【例【例1 1】求N！构造算法中的两个步骤：1）N!=N*(N-1)！2）0!=1，1!=1。递归算法如下：以n=3为例,调用过程如下：fact(3)-fact(2)-fact(1)-fac
17、t(2)-fact(3)递 归 回 溯迭代法介绍：迭代法介绍：用迭代方法估计递归算法的解用迭代方法估计递归算法的解,就是充分利用递归算法中就是充分利用递归算法中的递归关系的递归关系,通过确定的代数运算和数学分析的级数学问通过确定的代数运算和数学分析的级数学问,得到得到问题的困难度。问题的困难度。递归方程具体就是利用递归算法中的递归关系写出递归方递归方程具体就是利用递归算法中的递归关系写出递归方程程,迭代地绽开的右端，使之成为一个非递归的和式迭代地绽开的右端，使之成为一个非递归的和式,然后通过然后通过对和式的估计来达到对方程左端即方程的解的估计。对和式的估计来达到对方程左端即方程的解的估计。上节
18、上节 下节下节【例【例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)【例【例2 2】抽象地考虑以下困难一点的递】抽象地考虑以下困难一点的递归方程，且假设归方程，且假设n=2kn=2k，则迭代求解过，则迭代求解过程如下：程如下：=O(n)=O(n)一般地，当递归方程为：一般地，当递归方程为：T（n）=aT（n/c）+O(n)，T（n）的解为：）的解为：O(n)a1 时时 O(nlogcn)a
19、=c且且c1时时 O(nlogca)ac且且c1时时 在满足正确性、牢靠性、健壮性、可读性等质量因素的前下，设法提高算法的效率。看两组操作：(1)a=a+b；b=a-b；a=a-b；(2)t=a；a=b；b=t；2.2.3 2.2.3 提高算法质量提高算法质量两组操作的功能都是：“交换变量a、b中的数据”。虽然第一组操作节约了一个存储空间，但失去了可读性，是不行取的。下面给出一些原则上的建议：下面给出一些原则上的建议：1.1.保证正确性、牢靠性、健壮性、可读性；保证正确性、牢靠性、健壮性、可读性；1 1）当心那些视觉上不易辨别的操作符发生书写错误）当心那些视觉上不易辨别的操作符发生书写错误(与
20、与=)=)。2 2）算法中的变量）算法中的变量(指针、数组指针、数组)在当成右值运用（被引用）在当成右值运用（被引用）前，确定要有准确的含义，或是被赋值或是经模块接口前，确定要有准确的含义，或是被赋值或是经模块接口 传递信息。传递信息。3 3）算法中要当心变量发生上溢或下溢，数组的下标越界。）算法中要当心变量发生上溢或下溢，数组的下标越界。4 4）写算法时就要考虑，可能出现错误的状况，提示执行错）写算法时就要考虑，可能出现错误的状况，提示执行错 误处理算法。误处理算法。5 5）编写算法时区分问题的循环条件和停止条件，不要误用。）编写算法时区分问题的循环条件和停止条件，不要误用。6 6）留意算法
21、中循环体，或条件体的内容，不要误把循环体）留意算法中循环体，或条件体的内容，不要误把循环体 内的操作写互循环体外或者出现相反的错误。内的操作写互循环体外或者出现相反的错误。精品课件精品课件！精品课件精品课件！2 2提高效率。提高效率。1 1）以以提提高高算算法法的的全全局局效效率率为为主主，提提高高局局部部效效率率为为辅。辅。2 2）在在优优化化算算法法的的效效率率时时，应应当当先先找找出出限限制制效效率率的的“瓶颈瓶颈”。3 3）多多数数状状况况下下，时时间间效效率率和和空空间间效效率率可可能能是是对对立的，此时立的，此时 应当分析哪个更重要，作出适当的折衷。应当分析哪个更重要，作出适当的折
22、衷。4 4）可可以以考考虑虑先先选选取取合合适适的的数数据据结结构构，再再优优化化算算法。法。5 5）递递归归过过程程的的实实现现确确定定了了递递归归算算法法的的效效率率往往往往很低，费很低，费 时时和和费费内内存存空空间间。在在解解决决问问题题时时，假假如如能能运运用递推法用递推法 解决的，应考虑用递推法，其效率更高些。解决的，应考虑用递推法，其效率更高些。6 6）留意多用数学方法，可以大大提高算法效率。）留意多用数学方法，可以大大提高算法效率。7 7）另另外外还还有有一一些些细细微微环环节节上上的的问问题题,如如:乘乘、除除运算的效率比运算的效率比 加、减法运算低。加、减法运算低。上节上节 下节下节