算法设计与分析第2章 (I).ppt

第2章 算法分析基础,2023/10/21,成都学院计算机系,-2-,2.1 算法复杂度 2.2 渐近表示法 2.3 递推关系,2023/10/21,成都学院计算机系,-3-,主要知识点,掌握好算法的评价标准;了解影响程序运行时间的因素;掌握算法的评价标准:时间复杂度和空间复杂度的概念;掌握渐近时间复杂度的几种表示方式;掌握常见时间复杂度渐近表示之间的关系.,2.1 算法复杂度,2023/10/21,成都学院计算机系,-5-,2.1.1 什么是好的算法,好的算法 一个好的算法应具有以下4个重要特性:正确性（correctness）：算法的执行结果应当满足预先规定的功能和性能要求。简明性（simplicity）：算法应思路清晰、层次分明、容易理解、利于编码和调试。效率（efficiency）：算法应有效使用存储空间，并具有高的时间效率。最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。,2023/10/21,成都学院计算机系,-6-,程序健壮性 是指当输入不合法数据时，程序应能做适当处理而不至于引起严重后果。其含义是：当程序万一遇到意外时，能按某种预定方式做出适当处理。正确性和健壮性是相互补充的。,2023/10/21,成都学院计算机系,-7-,2.1.2 影响程序运行时间的因素,程序运行时间是指程序从开始到结束所需的时间。程序运行所需的时间依赖于计算机软、硬件系统。在完全相同的计算机环境下，影响程序运行时间的因素主要有：程序所依赖的算法；问题规模和输入数据；计算机系统性能。,2023/10/21,成都学院计算机系,-8-,算法效率的度量分为事前估计和后期测试。后期测试主要通过在算法中的某些部位插装时间函数来测定算法完成某一功能所需的时间。事前估计主要是分析算法的复杂性，包括空间复杂度和时间复杂度。算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。,2023/10/21,成都学院计算机系,-9-,1）事前分析目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况，包括：运用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间等。算法的执行时间=Fi*ti,2023/10/21,成都学院计算机系,-10-,频率计数 例：xx+y for i 1 to n do for i 1 to n do x x+y for j 1 to n do repeat x x+y repeat repeat(a)(b)(c)分析：(a)：xx+y执行了1次(b)：xx+y执行了n次(c)：xx+y执行了n2次 定义：频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。,2023/10/21,成都学院计算机系,-11-,一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间 如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。,2023/10/21,成都学院计算机系,-12-,数量级语句的数量级：语句的执行频率 例：1，n，n2算法的数量级：算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有n，n2，n3数 量级。若n=10，则可能的执行时间将分别是10，100，1000个单 位时间与环境因素无关。,2023/10/21,成都学院计算机系,-13-,计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n)注：最高次项与函数整体的关系空间特性分析（略）,2023/10/21,成都学院计算机系,-14-,2）事后测试目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图,2023/10/21,成都学院计算机系,-15-,2.1.3 算法的时间复杂度,抽象机模型 设抽象机提供由m个基本运算（也可称为语句）组成的运算集O=O1,O2,Om，每个运算都是基本的，它们的执行时间是有限常量。同时设执行第i个运算Oi所需的时间是i，1im。一个算法对于给定的抽象机上的一次执行过程，表现为执行一个基本运算的序列。,2023/10/21,成都学院计算机系,-16-,时间复杂度一个算法的时间复杂度（time complexity）是指算法运行所需的时间。设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n,I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为i，1im，i也是n和I的函数，记做i(n,I)。那么，算法A在输入为I时的运行时间是：,2023/10/21,成都学院计算机系,-17-,称为算法的时间复杂度。其中，输入数据I是问题的实例，n是问题的规模。要全面分析一个算法，需要考虑算法在最坏情况下的时间代价，在最好情况下的时间代价以及在平均情况下的时间代价。,2023/10/21,成都学院计算机系,-18-,最好、最坏和平均时间复杂度最好时间复杂度B(n)最坏时间复杂度W(n)平均时间复杂度A(n)Dn是规模为n的所有合法输入的集合，I和I*分别为Dn中算法运行最好和最坏情况的输入数据，P(I)是输入数据I在具体应用中被使用的概率。,2023/10/21,成都学院计算机系,-19-,2.1.4 使用程序步分析算法,一个程序步（program step）是指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。,2023/10/21,成都学院计算机系,-20-,【程序2-1】求数组元素累加之和的迭代程序float Sum(float list,const int n)float tempsum=0.0;count+;/针对赋值语句 for(int i=0;in;i+)count+;/针对for循环语句 tempsum+=listi;count+;/针对赋值语句 count+;/针对for的最后一次执行 count+;/针对return语句 return tempsum;,2023/10/21,成都学院计算机系,-21-,【程序2-2】求数组元素累加之和的递归程序float RSum(float list,const int n)count+;/针对 if 条件 if(n)count+;/针对 RSum 调用和return语句 return RSum(list,n-1)+listn-1;count+;/针对return语句 return 0;,2023/10/21,成都学院计算机系,-22-,设RSum（list,n）的程序步为T(n),T(n)=2+T(n-1)=2+2+T(n-2)=2*3+T(n-3)=2*n+T(0)=2*n+2,2023/10/21,成都学院计算机系,-23-,2.1.5 算法的空间复杂度,空间复杂度（space complexity）是指算法运行所需的存储空间。程序运行所需的存储空间包括以下两部分：固定空间需求（fixed space requirement）这部分空间与所处理数据的大小和个数无关，也就是说，与问题实例的特征无关。可变空间需求（variable space requirement）这部分空间大小与算法在某次执行中处理的特定数据的规模有关。,2.2 渐近表示法,2023/10/21,成都学院计算机系,-25-,算法渐近复杂性概念,T(n),当 n 时有:(T(n)-t(n)/T(n)0 t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，实质是T(n)略去低阶项留下的主项。它比T(n)简单。,2023/10/21,成都学院计算机系,-26-,例T(n)=3N2+4NlogN+7时,求它的一个渐近表达式 t(n)的一个答案是3N2,2023/10/21,成都学院计算机系,-27-,记：算法的计算时间为f(n)数量级限界函数为g(n)其中，n是输入或输出规模的某种测度。f(n)表示算法的“实际”执行时间与机器及语言有关。g(n)是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、与机器及语言无关的函数。以下给出算法执行时间：上界（）、下界（）、“平均”（）的定义。,2023/10/21,成都学院计算机系,-28-,2.2.1 渐近上界记号(O),如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)称为大O记号（big Oh notation）。使用大O记号及后面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度（asymptotic complexity）,2023/10/21,成都学院计算机系,-29-,例 1 f(n)=2n+3 是否等于O(n)当n3时，2n+33n 可选c=3，n0=3。对于nn0，f(n)=2n+33n。所以，f(n)=O(n)，即2n+3O(n)。,2023/10/21,成都学院计算机系,-30-,例2 f(n)=10n2+4n+2 的O表示形式.对于n2时,10n2+4n+210n2+5n 并且当n5时，5nn2 因此，可选c=11,n0=5；对于nn0，f(n)=10n2+4n+211n2所以f(n)=O(n2)。,2023/10/21,成都学院计算机系,-31-,例3 证明:f(n)=n！=O(nn)证:n！=n(n 1)(n 2)1 对于n1时,n(n 1)(n 2)1nn因此，可选c=1，n0=1 对于nn0，f(n)=n！nn 所以，f(n)=O(nn)。,2023/10/21,成都学院计算机系,-32-,例4 10n2+9 O(n)使用反证法假定存在c和n0，使得对于nn0，10n2+9cn始终成立，那么有10n+9/nc，即nc/10 9/(10n)总成立。但此不等式不可能总成立，取n=c/10+1时，该不等式便不再成立。,2023/10/21,成都学院计算机系,-33-,定理2-1 如果f(n)=amnm+am1nm1+a1n+a0是m次多项式，且am0，则f(n)=O(nm)。证明：取n0=1，当nn0时，有 f(n)=amnm+am1nm1+a1n+a0|am|nm+|am1|nm1+|a1|n+|a0|(|am|+|am1|/n+|a1|/nm1+|a0|/nm)nm(|am|+|am1|+|a1|+|a0|)nm取c=|am|+|am1|+|a1|+|a0|，定理得证。,2023/10/21,成都学院计算机系,-34-,只要适当选择关键操作，算法的渐近时间复杂度可以由关键操作的执行次数之和来计算。一般地，关键操作的执行次数与问题的规模有关，是n的函数。,2023/10/21,成都学院计算机系,-35-,【程序2-3】矩阵乘法for（i=0;in;i+）/n+1 for（j=0;jn;j+）/n(n+1)cij=0;/n2 for（k=0;kn;k+）/n2(n+1)cij+=aik*bkj;/n3,2023/10/21,成都学院计算机系,-36-,2.2.2 渐近下界记号(),如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作 f(n)=(g(n)称为记号（omega notation）。,2023/10/21,成都学院计算机系,-37-,例5 f(n)=2n+3=(n)对所有n，2n+32n 可选c=2，n0=0。对于nn0，f(n)=2n+32n 所以，f(n)=(n)，即2n+3(n)。,2023/10/21,成都学院计算机系,-38-,例6 f(n)=10n2+4n+2=(n2)对所有n，10n2+4n+210n2 可选c=10，n0=0 对于nn0，f(n)=10n2+4n+210n2 所以，f(n)=(n2)。,2023/10/21,成都学院计算机系,-39-,定理2-2 如果f(n)=amnm+am1nm1+a1n+a0是m次多项式，且am0，则f(n)=(nm)。（课后自己证明）,2023/10/21,成都学院计算机系,-40-,2.2.3 记号,如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)|f(n)|c2|g(n)|则记作f(n)=(g(n)称为记号（Theta notation）。(g(n)表示所有增长阶数与g(n)相同的函数的集合，用于表示一个算法运行时间具有与g(n)相同的阶。,2023/10/21,成都学院计算机系,-41-,例7 f(n)=2n+3=(n)，即2n+3(n)。例8 f(n)=10n2+4n+2=(n2)。定理2-3 如果f(n)=amnm+am1nm1+a1n+a0是m次多项式，且am0，则f(n)=(nm)。,2023/10/21,成都学院计算机系,-42-,2.2.4 小o记号,f(n)=o(g(n)当且仅当f(n)=O(g(n)且f(n)(g(n)o(g(n)表示所有增长阶数小于g(n)的所有函数的集合，用于表示一个算法运行时间f(n)的阶比g(n)低。例 f(n)=2n+3=o(n2)，即2n+3o(n2)。,2023/10/21,成都学院计算机系,-43-,渐近分析记号的性质,（1）传递性：f(n)=O(g(n)，g(n)=O(h(n)f(n)=O(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=o(g(n)，g(n)=o(h(n)f(n)=o(h(n)；,2023/10/21,成都学院计算机系,-44-,（2）反身性：f(n)=(f(n)；f(n)=O(f(n)；f(n)=(f(n).（3）对称性：f(n)=(g(n)g(n)=(f(n).（4）互对称性：f(n)=O(g(n)g(n)=(f(n)；,2023/10/21,成都学院计算机系,-45-,（5）算术运算：O(f(n)+O(g(n)=O(maxf(n),g(n)；O(f(n)+O(g(n)=O(f(n)+g(n)；O(f(n)*O(g(n)=O(f(n)*g(n)；O(cf(n)=O(f(n)；g(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)。,2023/10/21,成都学院计算机系,-46-,算法渐近复杂性分析中常用函数,（1）单调函数单调递增：m n f(m)f(n);单调递减：m n f(m)f(n);严格单调递增：m f(n).（2）取整函数 x：不大于x的最大整数；x：不小于x的最小整数。,2023/10/21,成都学院计算机系,-47-,取整函数的若干性质,x-1 0，有：n/a/b=n/ab;n/a/b=n/ab;a/b(a+(b-1)/b;a/b(a-(b-1)/b;f(x)=x,g(x)=x 为单调递增函数。,2023/10/21,成都学院计算机系,-48-,（3）多项式函数 p(n)=a0+a1n+a2n2+adnd；ad0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;,2023/10/21,成都学院计算机系,-49-,（4）指数函数 对于正整数m,n和实数a0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman=am+n;a1 an为单调递增函数;a1 nb=o(an),2023/10/21,成都学院计算机系,-50-,ex 1+x;|x|1 1+x ex 1+x+x2;ex=1+x+(x2),as x0;,2023/10/21,成都学院计算机系,-51-,（5）对数函数 log n=log2n;lg n=log10n;ln n=logen;logkn=(log n)k;log log n=log(log n);for a0,b0,c0,2023/10/21,成都学院计算机系,-52-,2023/10/21,成都学院计算机系,-53-,|x|1 for x-1,for any a 0,logbn=o(na),2023/10/21,成都学院计算机系,-54-,2.2.5 算法按时间复杂度分类,算法按计算时间分类凡渐近时间复杂度有多项式时间限界的算法称做多项式时间算法（polynomial time algorithm），而渐近时间复杂度为指数函数限界的算法称做指数时间算法（exponential time algorithm）。,2023/10/21,成都学院计算机系,-55-,最常见的多项式时间算法的渐近时间复杂度 O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)最常见的指数时间算法的渐近时间复杂度 O(2n)O(n！)O(nn),2023/10/21,成都学院计算机系,-56-,2023/10/21,成都学院计算机系,-57-,2.3 递推关系,2023/10/21,成都学院计算机系,-59-,2.3.1 递推方程,递推方程（recurrence equation）是自然数上一个函数T(n)，它使用一个或多个小于n时的值的等式或不等式来描述。递推方程也称为递推关系或递推式。递推方程必须有一个初始条件（也称边界条件）。,2023/10/21,成都学院计算机系,-60-,2.3.2 替换方法,替换方法要求首先猜测递推式的解，然后用归纳法证明。例 使用替换方法分析程序1-6。可以先对以下这些小的示例进行计算：T(3)=7=23 1；T(4)=15=24 1；T(5)=31=25 1；T(6)=63=26 1看起来，似乎T(n)=2n 1，n1。,2023/10/21,成都学院计算机系,-61-,证明：（归纳法证明）当n=1时，T(1)=1，结论成立。归纳法假设：当kn时，有T(k)=2k 1，那么，当k=n时，T(n)=2T(n 1)+1=2(2n1 1)+1=2n 1。因此，对所有n1，T(n)=2n 1=(2n)。,2023/10/21,成都学院计算机系,-62-,2.3.3 迭代方法,迭代方法的思想是扩展递推式，将递推式先转换成一个和式，然后计算该和式，得到渐近复杂度。例2-12 使用迭代方法分析程序1-6。函数Hanoi中两次调用自身，函数调用使用的实在参数均为n 1，函数Move所需时间具有常数界(1)，可以将其视为一个程序步，于是有：,2023/10/21,成都学院计算机系,-63-,扩展并计算此递推式：T(n)=2T(n 1)+1=2(2T(n 2)+1)+1=22T(n 2)+2+1=23T(n 3)+22+2+1=2n1T(1)+22+2+1=2n1+22+2+1=2n 1,2023/10/21,成都学院计算机系,-64-,使用递归树（recursion tree）可以形象地看到递推式的迭代过程。例2-13 T(n)=2T(n/2)+n的递归树,2023/10/21,成都学院计算机系,-65-,例2-14 T(n)=T(n/3)+T(2n/3)+n的递归树,