第二章 算法分析基础.ppt

第二章第二章 算法分析基础算法分析基础 2.1 引论引论 2.2 算法时间复杂性的分析方法算法时间复杂性的分析方法 2.3 时间与空间分析时间与空间分析第二章第二章 算法分析基础算法分析基础2.1 引论引论 评估算法性能的评估算法性能的5条准则条准则 正确性正确性 时间复杂性时间复杂性 占用空间占用空间(指令、数据和环境栈空间指令、数据和环境栈空间)可读性可读性 坚固性坚固性(健壮性健壮性)还应该具有还应该具有灵活性灵活性、可重用性可重用性和和自适应性自适应性。1正确性正确性一个算法包括两方面内容：一是解决问题的一个算法包括两方面内容：一是解决问题的方法，二是实现这一方法的一系列指令（语句、方法，二是实现这一方法的一系列指令（语句、步骤）。步骤）。vv确认一个算法所用方法和（或）所用公式的正确认一个算法所用方法和（或）所用公式的正确性，可能需要相关的引理和定理。确性，可能需要相关的引理和定理。vv证明一系列语句确实做了符合规定的操作。证明一系列语句确实做了符合规定的操作。vv正确性的验证：测试和证明。正确性的验证：测试和证明。“正确正确”的含义在通常的用法中有很大的差的含义在通常的用法中有很大的差别，大体可分为以下四个层次：别，大体可分为以下四个层次：算法不含语法错误；算法不含语法错误；算法对于几组输入数据能够得出满足规算法对于几组输入数据能够得出满足规格说明要求的结果；格说明要求的结果；算法对于精心选择的典型、苛刻而带有算法对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要刁难性的几组数据能够得出满足规格说明要求的结果；求的结果；算法对一切合法的输入数据都能产生满算法对一切合法的输入数据都能产生满足规格说明要求的结果。足规格说明要求的结果。Testing(测试测试)vvBlack Box Methods 黑盒法黑盒法侧重测试程序的功能，不考虑程序是侧重测试程序的功能，不考虑程序是如何实现的，即代码结构。如何实现的，即代码结构。设计测试用例，检查是否能得到预想设计测试用例，检查是否能得到预想的结果。的结果。vvWrite Box Methods 白盒法白盒法侧重测试程序的代码结构侧重测试程序的代码结构Statement Coverage 语句覆盖语句覆盖:使程使程序中的每一条语句都至少执行一次。序中的每一条语句都至少执行一次。Decision Coverage 分支覆盖分支覆盖：使程：使程序中的每一个分支都至少执行一次。序中的每一个分支都至少执行一次。yesno2时间复杂性时间复杂性 度量算法的标准：度量算法的标准：（1）能告诉算法所采用的方法的时间效率；）能告诉算法所采用的方法的时间效率；（2）与算法描述语言及设计风格无关；）与算法描述语言及设计风格无关；（3）与算法的许多细节无关；）与算法的许多细节无关；（4）足够精确和具有一般性。）足够精确和具有一般性。基本运算（关键操作）基本运算（关键操作）对所研究问题的基本操作对所研究问题的基本操作时间复杂性时间复杂性一个算法的一个算法的时间复杂性时间复杂性是指该算法的基本运算次数。是指该算法的基本运算次数。3占用的存储空间占用的存储空间包括存储算法本身所占用的存储空间（指令空间），包括存储算法本身所占用的存储空间（指令空间），算法的输入、输出数据所占用的存储空间和算法运算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间（数据空间）行过程中临时占用的存储空间（数据空间）和环境和环境栈空间。栈空间。算法在运行过程中所占用的存储空间的大小被定义算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。分。算法的空间复杂性一般以数量级的形式给出。4 4可读性可读性可读性可读性 最最最最简简简简单单单单和和和和最最最最直直直直接接接接的的的的算算算算法法法法虽虽虽虽然然然然不不不不是是是是最最最最有有有有效效效效的的的的，但但但但却却却却具具具具有有有有良良良良好好好好的的的的可可可可读读读读性性性性。可可可可读读读读性性性性好好好好的的的的算算算算法法法法使使使使得得得得证证证证明明明明其其其其正正正正确确确确性性性性比比比比较较较较容容容容易易易易，同同同同时时时时便便便便于于于于编编编编写写写写、修修修修改改改改、阅阅阅阅读读读读和和和和调调调调试试试试，所所所所以以以以还还还还是是是是应应应应当当当当强强强强调调调调和和和和不不不不容容容容忽忽忽忽视视视视的的的的。不不不不过过过过对对对对于于于于那那那那些些些些需需需需要要要要经经经经常常常常使使使使用用用用的的的的算算算算法法法法来来来来说说说说，高高高高效效效效率率率率（即即即即尽尽尽尽量量量量减减减减少少少少运运运运行行行行时时时时间间间间和和和和压压压压缩存储空间）比可读性更为重要。缩存储空间）比可读性更为重要。缩存储空间）比可读性更为重要。缩存储空间）比可读性更为重要。5 5坚固性坚固性坚固性坚固性好的算法还应该具有好的算法还应该具有好的算法还应该具有好的算法还应该具有可移植性可移植性可移植性可移植性易用性易用性易用性易用性安全性安全性安全性安全性灵活性灵活性灵活性灵活性可重用性可重用性可重用性可重用性自适应性自适应性自适应性自适应性可靠性可靠性可靠性可靠性6.最优算法定义如下：最优算法定义如下：某算法某算法A为最优，当且仅当被研究的解决为最优，当且仅当被研究的解决同一领域同一问题的所有算法集合同一领域同一问题的所有算法集合SA(A SA)中没有一个算法执行的基本运算次数比中没有一个算法执行的基本运算次数比算法算法A更少。更少。第二章第二章 算法分析基础算法分析基础2.2 算法时间复杂性的分析方法算法时间复杂性的分析方法问题：决定程序（算法）运行时间的因素有哪些？问题：决定程序（算法）运行时间的因素有哪些？基本运算次数基本运算次数 平均运算次数平均运算次数 加权平均加权平均定义定义定义定义2.12.1 设一个领域问题的输入的规模设一个领域问题的输入的规模设一个领域问题的输入的规模设一个领域问题的输入的规模为为为为n n，DnDn是该领域是该领域是该领域是该领域问题的所有输入的集合，任一输入问题的所有输入的集合，任一输入问题的所有输入的集合，任一输入问题的所有输入的集合，任一输入I IDnDn，P(I)P(I)是是是是I I出出出出现的频率，现的频率，现的频率，现的频率，P(I)=1 P(I)=1，T(I)T(I)是（解决该领域问题的）算是（解决该领域问题的）算是（解决该领域问题的）算是（解决该领域问题的）算法在输入法在输入法在输入法在输入I I下所执行的基本运算次数。我们定义该算法下所执行的基本运算次数。我们定义该算法下所执行的基本运算次数。我们定义该算法下所执行的基本运算次数。我们定义该算法的期望复杂性为：的期望复杂性为：的期望复杂性为：的期望复杂性为：E(n)=P(I)*T(I)E(n)=P(I)*T(I)该算法的最坏复杂性为：该算法的最坏复杂性为：该算法的最坏复杂性为：该算法的最坏复杂性为：W(n)=maxT(I)W(n)=maxT(I)例例2.1 A是一个含有是一个含有n个不同元素的实数数组，给出个不同元素的实数数组，给出求求A之最大和最小元素的算法。之最大和最小元素的算法。算法算法SM(A,n.max,min)SM1初始化初始化 maxminA1.SM2比较比较 FOR I=2 to n DO /2*(n-2+1)次元素的比较（基次元素的比较（基本运算）本运算）(IF AI max THEN maxAI.IF AI min THEN minAI).算法算法SM的时间复杂性为的时间复杂性为2(n-1)。例例 2.2 实数数组实数数组R由由n个元素组成，给定一个实数个元素组成，给定一个实数K，试确定试确定K是否是是否是R的元素。的元素。算法算法F(R,n,K.i)F1 初始化初始化 i 1.F2 比较比较 WHILE in DO (IF Ri=K THEN RETURN.i i+1).n 1时时 最少比较次数：最少比较次数：1成功成功 最大比较次数：最大比较次数：n:成功，失败（最坏复杂性）成功，失败（最坏复杂性）R1 R2 R3 R4 R5 R6 R7 R85 20 12 7 30 40 25 16K=Ri q/nK!=Ri 1-q设设q（0q1）表示表示K 在在R中的概率，中的概率，q通过计算我们可以得到算法通过计算我们可以得到算法F的期望复杂性为的期望复杂性为 E(n)=P(I)*T(I)=(q/n)*1+(q/n)*2+(q/n)*n+(1-q)*n n项项 1项项 =1/2(n+1)q+(1-q)n 如果已知如果已知K在在R中，即中，即q=1，则有则有 E(n)=1/2(n+1)由算法由算法F可以很容易看出该算法的最坏复杂性为可以很容易看出该算法的最坏复杂性为 W(n)=maxT(i)|1i n+1=n 例例2.3 算法算法算法算法SMSM的改进算法的改进算法的改进算法的改进算法BS BS。算法算法算法算法BSBS（A A，i i，j.j.fmaxfmax ，fminfmin）/在数组在数组在数组在数组A A的第的第的第的第i i个元素到第个元素到第个元素到第个元素到第j j个元素之间寻找最大和最个元素之间寻找最大和最个元素之间寻找最大和最个元素之间寻找最大和最/小元素，已知小元素，已知小元素，已知小元素，已知i i j j。BS1 BS1 递归出口递归出口递归出口递归出口 IF i=j THEN IF i=j THEN（fmaxfminAifmaxfminAi.RETURN.RETURN.）IF i=j IF i=j 1 THEN 1 THEN（IF Ai Aj THENIF Ai Aj THEN（fmaxAj.fminAifmaxAj.fminAi）.ELSE ELSE（fmaxAifmaxAi.fminAjfminAj）.RETURN RETURN）.BS2 取中值取中值 midBS3 递归调用递归调用 BS（A，i，mid.gmax，gmin）BS（A，mid+1，j.hmax，hmin）.BS4 合并合并fmaxmaxgmax，hmax.fminmingmin，hmin.i=1 mid=2 j=4 i=5 mid=6 j=8 A1 A2 A3 A4 A5 A6 A7 A85 20 12 7 30 40 25 16i=1 j=2 i=3 j=4 A1 A2 A3 A45 20 12 7i=5 j=6 i=7 j=8 A5 A6 A7 A830 40 25 16i=1 mid=4 j=8 A1 A2 A3 A4 A5 A6 A7 A85 20 12 7 30 40 25 161234567在刚才的递归表达式中，在刚才的递归表达式中，当当n n是是2 2的幂时的幂时（即存在正整数，使得（即存在正整数，使得 ）有）有BS与与SM的比较的比较 虽然算法虽然算法SMSM和算法和算法BSBS的时间复杂性的时间复杂性均为线性型，但因均为线性型，但因 ，故就计算时间而言，算法故就计算时间而言，算法BSBS优于算法优于算法SMSM。然而算法然而算法BSBS是递归算法，因此它的实现是递归算法，因此它的实现需要额外的辅助空间栈。需要额外的辅助空间栈。例例 2.4 For i=1 To i=n Do xx+1.例例 2.5 For i=1 To i=n Do For j=1 To j=n Do xx+1.T(n)=nT(n)=n2函数数量级的渐进表示函数数量级的渐进表示定义定义2.2 设设f(n)和和g(n)是正整数集到正实数集上的是正整数集到正实数集上的函数，定义：函数，定义：（1）称）称g(n)的阶至少为的阶至少为f(n)，当且仅当存在一个，当且仅当存在一个正的常数正的常数C和和n0，使得对任意使得对任意的的nn0，有，有g(n)C f(n)记记 g(n)为为(f(n)符号定义了函数符号定义了函数符号定义了函数符号定义了函数g g g g的一个下限。的一个下限。的一个下限。的一个下限。n n n n 是实例特征，如：输入、输出的规模，数组的维数，是实例特征，如：输入、输出的规模，数组的维数，是实例特征，如：输入、输出的规模，数组的维数，是实例特征，如：输入、输出的规模，数组的维数，图的边数等；图的边数等；图的边数等；图的边数等；一个算法一个算法一个算法一个算法/程序时间复杂性是程序时间复杂性是程序时间复杂性是程序时间复杂性是(f(n(f(n(f(n(f(n)，在给定的，在给定的，在给定的，在给定的n n n n下，下，下，下，该算法的运行时间总是大于该算法的运行时间总是大于该算法的运行时间总是大于该算法的运行时间总是大于|f(nf(nf(nf(n)|)|)|)|的一个常数倍。的一个常数倍。的一个常数倍。的一个常数倍。（2）称）称g(n)的阶至多为的阶至多为f(n)，当且仅当存在，当且仅当存在一个正常数一个正常数C和和n0，使得对任意的，使得对任意的nn0，有，有g(n)C f(n)记记 g(n)为为(f(n)大写大写大写大写O O O O 符号定义了函数符号定义了函数符号定义了函数符号定义了函数g g g g的一个上限的一个上限的一个上限的一个上限(upper-(upper-(upper-(upper-bound)bound)bound)bound)；一个算法一个算法一个算法一个算法/程序时间复杂性是程序时间复杂性是程序时间复杂性是程序时间复杂性是O(f(nO(f(nO(f(nO(f(n)，称其时间，称其时间，称其时间，称其时间复杂性的阶为复杂性的阶为复杂性的阶为复杂性的阶为f(nf(nf(nf(n)，在给定的，在给定的，在给定的，在给定的n n n n下，该算法的运行下，该算法的运行下，该算法的运行下，该算法的运行时间总是小于时间总是小于时间总是小于时间总是小于|f(nf(nf(nf(n)|)|)|)|的一个常数倍。的一个常数倍。的一个常数倍。的一个常数倍。（3）称）称g(n)的阶为的阶为f(n)，当且仅当存在正常，当且仅当存在正常数数C1、C2和和n0，使得对任意的，使得对任意的n n0，有，有C1f(n)g(n)C2f(n)记记 g(n)为为(f(n)符号定义了函数符号定义了函数g g的上限和下限。的上限和下限。一个算法一个算法/程序时间复杂性是程序时间复杂性是(f(n(f(n)意味着，该意味着，该算法在最好和最坏情况下的计算时间就一个常数算法在最好和最坏情况下的计算时间就一个常数因子范围内是相同的。因子范围内是相同的。(1)(1)g(n)=8n+128g(n)=8n+128，f(n)=nf(n)=n2 2寻找正常数寻找正常数寻找正常数寻找正常数c c和和和和n n0 0满足满足满足满足g(n)=cng(n)=cn2 2令令令令8n+128=n8n+128=0-8n 128=0(n-16)(n+8)=0(n-16)(n+8)=0则则则则n n0 0=16=16，c=1 g(n)=O(nc=1 g(n)=O(n2 2)(2)(2)g(n)=5 ng(n)=5 n2 2 64n+256 64n+256，f(n)=nf(n)=n2 2寻找正常数寻找正常数寻找正常数寻找正常数c c和和和和n n0 0满足满足满足满足g(n)=cng(n)=cn2 2令令令令5n5n2 2 64n+256 64n+256=n=n2 24(n-8)4(n-8)2 2=0=0则则则则n n0 0=0=0，c=1 c=1 g(ng(n)=)=(n(n2 2)例例2 For i=1 To i=n Do xx+1.例例3 For i=1 To i=n Do For j=1 To j=n Do xx+1.T(n)=n=O(n)T(n)=n2=O(n2)例例1 T(n)=(n+1)2 n0=1,c=4时，当时，当n=n0时，时，(n+1)2=(2n)2=4n2,则则T(n)=O(n2)例例4 For i=1 To i=n Do For j=1 To j=m Do xx+1.则则T(n)=n*m=O(n*m)O(1),O(n),O(nO(1),O(n),O(n2 2)O(n)O(n3 3),O(n),O(nmm),O(2),O(2n n)常数常数常数常数 线性阶线性阶线性阶线性阶 多项式阶多项式阶多项式阶多项式阶 指数阶指数阶指数阶指数阶定理定理定理定理2.1 2.1 若若若若 A(n)=A(n)=a ammn nmm+a+a1 1n+a n+a 是关于是关于是关于是关于n n的的的的mm次多次多次多次多项式，则项式，则项式，则项式，则 A(n)=(nA(n)=(nmm)事实上，事实上，事实上，事实上，当当n很大时，有如下关系成立很大时，有如下关系成立因此，有因此，有算法分成两类：多项式阶算法和指数阶算法。算法分成两类：多项式阶算法和指数阶算法。第二章第二章 算法分析基础算法分析基础2.3 时间与空间分析时间与空间分析 一个算法在一个算法在不同的执行时间内不同的执行时间内，它，它占用的内存空间量占用的内存空间量不一定相等不一定相等，占用空间量，占用空间量y是时间是时间x的函数，即的函数，即y=f(x)。称积分称积分 为该算法的时空积分，其中为该算法的时空积分，其中t是该算法的是该算法的执行时间。基于时空积分，可以比较算法优劣，时空积执行时间。基于时空积分，可以比较算法优劣，时空积分较小的算法较优。分较小的算法较优。例例如如，一一个个算算法法执执行行时时间间为为30秒秒，前前10秒秒算算法法占占用用60个个字字节节，第第二二个个10秒秒算算法法占占用用70个个字字节节，最最后后10秒秒算算法法占占用用80个个字字节节。该该算算法法的的时时空分布如图空分布如图2.2所示。所示。807060302010YX效率效率图图2.2 时空分布示意图时空分布示意图显然算法的时空积分为显然算法的时空积分为60*10+70*10+80*10=2100（字节秒）（字节秒）基于时空积分，我们可以比较算法基于时空积分，我们可以比较算法SMSM和算法和算法BSBS的的优劣，时空积分较小的算法是较优的算法。优劣，时空积分较小的算法是较优的算法。图图2.3 算法算法SM与算法与算法BS的时空积分比较图的时空积分比较图（b）算法算法BS的时空图的时空图(a)算法算法SM的时空图的时空图算法需要算法需要的空间的空间算法需要算法需要的空间的空间SYTXBSYTXLSM比比BS多用的时间多用的时间BS比比SM多多占占用用 的的 空空间间算算法法SM的的计计算算时时间间为为L，占占用用空空间间为为S；算算法法BS的的计计算算时时间为间为T（T S）。）。当当n比较大时，比较大时，算法，算法BS优于算法优于算法SM 作业作业指出下面结论正确与否，并说明理由：指出下面结论正确与否，并说明理由：(1)5n2-6n=(n2)(2)2n22n+nlogn=(n22n)(3)6n3/(logn+1)=O(n3)(4)10n2+9=O(n)(5)n2logn=(n2)(6)n2/logn=(n2)第二章第二章 总结总结评判算法的评判算法的评判算法的评判算法的5 5 5 5条准则（条准则（条准则（条准则（正确性正确性正确性正确性和和和和时间复杂性时间复杂性时间复杂性时间复杂性）时间复杂性分析（时间复杂性分析（时间复杂性分析（时间复杂性分析（基本运算次数基本运算次数基本运算次数基本运算次数）算法算法算法算法SMSMSMSM和和和和算法算法算法算法BSBSBSBS（递归思想）递归思想）递归思想）递归思想）算法算法算法算法F F F F函数函数函数函数g(n)g(n)g(n)g(n)的阶的研究（的阶的研究（的阶的研究（的阶的研究（g(n)g(n)g(n)g(n)的阶取决于的阶取决于的阶取决于的阶取决于阶最高的项阶最高的项阶最高的项阶最高的项，与其系数和其它较低阶项无关）与其系数和其它较低阶项无关）与其系数和其它较低阶项无关）与其系数和其它较低阶项无关）算法的时空分析算法的时空分析算法的时空分析算法的时空分析练习题练习题如何评价一个算法？如何评价一个算法？计算计算f=1！+2！+3！+n！的时间复杂性的时间复杂性void factorsum（int n）int i，j；int f，w；f=0；for（i=1;i=n;i+）w=1；for（j=1;j=i;j+）w=w*j;f=f+w;return；