第二章算法分析基础.ppt

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

1、 第 二 章 算 法 分 析 基 础 算法分析的任务:对设计出的每一个具体的算法,利用数学工具，讨论其复杂度。上节 下节2.1 2.1 算法分析体系及计量算法分析体系及计量对算法的评价算法的评价有两个大的方面：一是人对算法的维护的方便性。二是算法在实现运行时占有的机器资源的多少即算法的运行的时间和空间效率。上节 下节2.1.1 2.1.1 算法分析的评价体系算法分析的评价体系 人对算法的维护主要有编写、调试、改正和功能扩充等工作,这就需要在算法设计时注重算法的可可读读性性。为了算法的利用率,也要考虑算法的适适用用范围范围,注重算法的通用性通用性、可重用性可重用性和可扩充性可扩充性。机器对算法的

2、运行效率主要包括时间效率和空间效率。算法在完成功能的前题下最好是占用空间少而且执行时间短。另外在算法实现时,要考虑算法在运行过程中与使用者进行交互的情况。这就要求,算法的交互部分要具有友好性友好性和健壮性健壮性。上节 下节 总之，对算算法法的的分分析析和和评评价价，一般应考虑正确性、可维护性、可读性、运算量及占用存储空间等诸多因素。其中评价算法的三条主要标准标准是：(1)算法实现所耗费的时间时间；(2)算法实现所所耗费的存储空间空间，其中 主要考虑辅助存储空间；(3)算法应易于理解理解，易于编码，易于调 试等等。上节 下节 1.1.和算法执行时间相关的因素和算法执行时间相关的因素：1）问题中数

3、据存储的数据结构2）算法采用的数学模型 3）算法设计的策略4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度 上节 下节2.1.2 2.1.2 算法的时间复杂性算法的时间复杂性2 2算法效率的衡量方法算法效率的衡量方法 通常有两种衡量算法效率衡量算法效率的方法:1）事后统计法（有缺点，较少使用）2）事前分析估算法 算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=(f(n)T(n)=(f(n),称 T(n)为 算 法 的 渐渐 近近 时时 间间 复复 杂杂 度度(Asy

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

5、，语句“j=1、k=1”的频度是1，语句“j=n;+j”的频度是n。算法运行时间为：3*n2+2n+2。上节 下节 对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基基本本(或或者者说说是是主主要要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。例如：例如：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+a

6、i,k*bk,j;ci,j=ci,j+ai,k*bk,j;该算法的基本操作是乘法操作,时间复杂度为n3 3。上节 下节 当一个算法的算法运行时间为n2+n+1时，由于n2+n+1与n2的数量级相等(该表达式当n足够大时约等于n2),我们说这个算法的渐进时间复杂度算法的渐进时间复杂度(简称算法的时间复算法的时间复杂度杂度)为：T(n)=O(n2)。数量级相等是这样定义的,设f(n)是一个关于正整数n 的函数,若存在一个常数C，使 则称f(n)与g(n)是同数量级的函数。上节 下节算法(渐进渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：(1)称为常数级 (log

7、n)称为对数级 (n)称为线性级 (nc c)称为多项式级 (cn n)称为指数级 (n!)称为阶乘级 上节 下节 以上时间复杂度级别是由低到高排列的,其随规模n的增长率，由图2-1可见一斑：图2-1 T(n)与规模n的函数关系上节 下节 一般来说如果选用了阶乘级的算法，则当问题规模等于或者大于10时就要认真考虑算法的适用性问题算法的适用性问题。所以,原则上一个算法的时间复杂度,最好不要采用指数级和阶乘级的算法,而应尽可能选用多项式级或线性级等时间复杂度级别较小的算法。对于较复杂的算法，可将它分隔成容易估算的几个部分，然后再利用O的求和原则得到整个算法的时间复杂度。例：若算法的两个部分的时间复

8、杂度分别为 T1(n)=O(f(n)和 T2(n)=O(g(n)，则总的时间复杂度为：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)。上节 下节4 4问题时间复杂度的上界和下界问题时间复杂度的上界和下界 复杂度的上界和下界是用以估计问题所需某资源的复杂程度的界限函数。如果找到解某问题的算法,其资源的复杂度为u(n),则u(n)是问题本身复杂度的一个上界上界。如果对任何算法，其复杂度都必需大于l(n)，则l(n)是问题复杂度的一个下界下界。上节 下节 定义定义1:1:如果存在两个正常数如果存在两个正常数c c和和n0n0，对于所有的对于所有的n=n0,n=n0,有有|f(n)|

9、c|g(n)|f(n)|c|g(n)|，则记作则记作 :f(n)=(g(n)f(n)=(g(n)。定义定义2 2：如果存在两个正常数：如果存在两个正常数c c和和n0n0，对于所有的对于所有的nn0nn0，有有|f(n)|c|g(n)|,f(n)|c|g(n)|,则记作则记作 :f(n)=(g(n)f(n)=(g(n)。定义定义3 3：当：当 f(N)=(g(N)f(N)=(g(N)且且 f(N)=(g(N)f(N)=(g(N)时，则记时，则记 f(N)=(g(N)f(N)=(g(N)。也就是说也就是说f(N)f(N)与与g(N)g(N)同阶。同阶。定义定义4 4：如果对于任意给定的：如果对于

10、任意给定的S0S0，都存在非负整数都存在非负整数N0N0，使使得当得当NN0NN0时有时有f(N)f(N)SgSg(N)(N)，则称函数则称函数f(N)f(N)当当N N充分大时，比充分大时，比g(N)g(N)低阶，记为低阶，记为f(N)=o(g(N)f(N)=o(g(N)。定义定义5:5:若若g(N)=o(f(N),g(N)=o(f(N),即当即当N N充分大时充分大时,f(N)f(N)的阶比的阶比g(N)g(N)高，则记高，则记f(N)=W(g(N)f(N)=W(g(N)。上节上节 下节下节5.5.算法时间复杂度的最好情况和最坏情况算法时间复杂度的最好情况和最坏情况 我们要确定能反映出算法

11、在各种情况下工作的数据集,选取的数据要能够反映、代表各种计算情况下的估算,包括最好情况下的时间复杂度(时间复杂度下界,一般记为Tmax)、最坏情况下的时间复杂度(时间复杂度上界,一般记为Tmin)、平均情况下的时间复杂度(一般记为Tavg)和有代表性的情况,通过使用这些数据配置来运行算法,以了解算法的性能。上节 下节 以上三种情况下的时间复杂性,各从某一个角度来反映算法的效率,各有各的用处,也各有各的局限性。但实践表明可操作性最好的,且最有实际价值的,是最坏情况下的时间复杂性。一般来说,最好情况和最坏情况的时间复杂性是很难计量的。有时也按平均情况计量时间复杂性，但要对输入不同数据的概率做人为的

12、假设(一般是假设等概率)之后才能进行,所做的假设缺乏必要的根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。上节 下节算法的存储量包括：1)输入数据所占空间；2)算法本身所占空间；3)辅助变量所占空间。上节 下节2.1.3 2.1.3 算法的空间复杂性算法的空间复杂性 研究算法的空间效率，只需要分析除输入和算法之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作,否则,它应当是规模的一个函数。算法的空间复杂度是指算法在执行过程中所占辅助存储空间的大小(也有课本定义为所占全部存储空间的大小),用S(n)表示。与算法的时间复杂度相同，算法的空间复杂度

13、S(n)也可表示为:S(n)=(g(n)表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。上节 下节 NP完全性问题属于“计算复杂性”研究的课题。所谓计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)。二是计算所需的存储单元数量(这叫空间复杂度)。上节 下节2.1.42.1.4NPNP完全问题完全问题 问题的复杂性和算法的复杂性的区别：只就时间复杂性说，算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度。如果一个判定性问题的复杂度是该问题的一个实例的规

14、模n 的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。上节 下节 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题,亦称为易验证问题类。特 殊 的 NP问 题 就 是 NP完 全 问 题(NPC问 题,C代 表complete)。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立!一般认为NPC问题是难解的问题类。简单地说，存在多项式时间的算法的一类问题，称之

15、为P类问题，而像梵塔问题、推销员旅行问题等问题，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。上节 下节 复杂性理论中最具理论意义的当数NP完全性问题，这类问题在下述意义下具有同等的难度：即要么每个NP完全问题都存在多项式时间的算法（即通常所指的有效算法）；要么所有NP完全问题都不存在多项式时间的算法。目前已知的NP完全问题就有2000多个,其中有许多是非常重要的问题,如:货郎问题、调度问题、最大团问题、最大独立集问题、Steiner树问题、背包问题、装箱问题、等等。上节 下节 在图上定义的许多组合优化问题是NP完全问题。这类问题属于较难解的问题，至今没有找到多项式时间算法，也很可

16、能根本没有多项式时间算法。遇到这类问题时，通常从以下几个方面来考虑并寻求解决办法:1)特殊情形特殊方法 2)动态规划和分枝限界方法 3)概率分析 4)近似算法 5)启发式算法 上节 下节 一具体算法的时间复杂度和空间复杂度往往是不独立的，在算法设计中要在时间效率和空间效率之间折衷。上节 下节2.2 2.2 算法分析实例算法分析实例 1 1仅依赖于问题规模的时间复杂度仅依赖于问题规模的时间复杂度 有一类简单的问题，其操作具有普遍性，也就是说对所有的数据均等价地进行处理，这类算法的时间复杂度，很容易分析。【例1】【例2】【例3】上节 下节2.2.1 2.2.1 非递归算法分析非递归算法分析【例1】

17、交换i和j的内容。Temp=i；i=j；j=temp；以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是(1)。上节 下节【例【例2 2】变量计数之一变量计数之一。(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)。当有若干个循环语句时，算法的时间复杂度是由嵌

18、套层数最多的循环语句中最内层语句的频度f(n)决定的。上节 下节【例【例3 3】变量计数之二变量计数之二。(1)x=1；(2)for(i=1；i=n；i+)(3)for(j=1；j=i；j+)(4)for(k=1；k=0 and Aik)(2)while(i=0 and Aik)(3)i=i-1 (3)i=i-1；(4)return i (4)return i；上节上节 下节下节 此此算法的频度算法的频度不仅与问题规模不仅与问题规模n n有关，还与输入实有关，还与输入实例中例中A A的各元素取值及的各元素取值及k k的取值有关：的取值有关：1.1.若若A A中没有与中没有与k k相等的元素，则

19、语句相等的元素，则语句(2)(2)的频度的频度f(n)=nf(n)=n；这是最坏情况。这是最坏情况。2.2.若若A A的最后一个元素等于的最后一个元素等于k,k,则语句则语句(2)(2)的频度的频度f(n)f(n)是常数是常数1;1;这是最这是最好好情况。情况。上节 下节 在求平均情况时，一般地假设查找不同元素的概率P是相同的,则算法的平均复杂度为：若对于查找不同元素的概率P不相同时，其算法复杂度就只能做近似分析，或在构造更好的算法或存储结构后，做较准确的分析。上节 下节 一进一步认识递归 1执行过程 【例1】求N！2实现机理简介 二效率分析方法 1代入法代入法 2迭代法 3套用公式法 4差分

20、方程法 5母函数法 上节 下节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)-fact(2)-fact(3)递 归 回 溯 上节 下节迭代法迭代法介绍：用迭代方法估计递归算法的解,就是充分利用递归算法中的递归关系,通过一定的代数运算和数学分析的级数知识,得到问题的复杂度。递归方程具体就是利用递归算法中的递归关系写出递归方程,迭代地展开的右端，使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端即方程的解

21、的估计。【例【例2 2】【例【例3 3】【例【例4 4】上节 下节【例【例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=2k，则迭代求解过程如下：上节 下节【例【例3 3】以下递归方程，是第四章将介绍的二分算法典型的递归方程。同样假设n=2k：T(n)=T(n/2)+O(n)=T(n/4)+O(1)+O(n)=O(n)+O(n)+

22、O(n)+O(n)=k*O(n)=O(n*log2n)若递归次数再多一些,或递归阶再大一些,如:T(n)=2*T(n/2)+O(n)等,得到的就不是线性的复杂性了，复杂性为O(n*log2n)。上节 下节一般地，当递归方程为：一般地，当递归方程为：T（n）=aT（n/c）+O(n)，T（n）的解为：的解为：O(n)a1 时时 O(nlogcn)a=c且且c1时时 O(nlogca)ac且且c1时时 首先要提醒大家，不要一味地追求算法的效率，应当在满足正确性、可靠性、健壮性、可读性等质量因素的前提下，设法提高算法的效率。看两组操作：(1)a=a+b；b=a-b；a=a-b；(2)t=a；a=b；

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

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