算法与复杂性-第2讲-算法分析基础课件.ppt

1、第第2章章 算法分析基础算法分析基础2.1 算法复杂度算法复杂度2.1.1 什么是好的算法什么是好的算法 一个好的算法应具有以下一个好的算法应具有以下4 4个重要特性个重要特性:正确性正确性（correctnesscorrectness）：算法的执行结果）：算法的执行结果应当满足预先规定的功能和性能要求。应当满足预先规定的功能和性能要求。简明性简明性（simplicitysimplicity）：算法应）：算法应思路清晰、层次分明、容易理解、思路清晰、层次分明、容易理解、利于编码和调试。利于编码和调试。效率效率（efficiencyefficiency）：算法应有效使用存）：算法应有效使用存储空

2、间，并具有高的时间效率。储空间，并具有高的时间效率。最优性最优性（optimalityoptimality）：算法的执行时间）：算法的执行时间已达到求解该类问题所需时间的下界。已达到求解该类问题所需时间的下界。是指当输入不合法数据是指当输入不合法数据 时，程序应能做适当处理而不至于时，程序应能做适当处理而不至于 引起严重后果。引起严重后果。其含义是：当程序其含义是：当程序 万一遇到意外时，能按某种预定方万一遇到意外时，能按某种预定方 式做出适当处理。式做出适当处理。正确性和健壮性是相互补充的。正确性和健壮性是相互补充的。2.1.2 影响程序运行时间的因素影响程序运行时间的因素 影响程序运行时间

3、的因素主要有：影响程序运行时间的因素主要有：程序所依赖的算法；程序所依赖的算法；问题规模和输入数据；问题规模和输入数据；计算机系统性能。计算机系统性能。2.1.3 算法的时间复杂度算法的时间复杂度 抽象机模型抽象机模型设抽象机提供由设抽象机提供由m m个基本运算（也可称为语句）个基本运算（也可称为语句）组成的运算集组成的运算集O=OO=O1 1,O,O2 2,O Om m，每个运算，每个运算都是基本的，它们的执行时间是有限常量。同都是基本的，它们的执行时间是有限常量。同时设执行第时设执行第i i个运算个运算O Oi i所需的时间是所需的时间是 i i，1im1im。时间复杂度时间复杂度一个算法

4、的时间复杂度（一个算法的时间复杂度（time complexity）是指）是指算法运行所需的时间。算法运行所需的时间。设有一个在抽象机上运行的算法设有一个在抽象机上运行的算法A，I是某次运行是某次运行时的输入数据，其规模为时的输入数据，其规模为n，则算法，则算法A的运行时间的运行时间T是是n和和I的函数，记做的函数，记做T(n,I)。又设在该次运算中抽。又设在该次运算中抽象机的第象机的第i个基本运算个基本运算Oi的执行次数为的执行次数为 i，1im，i也是也是n和和I的函数，记做的函数，记做 i(n,I)。那么，算法。那么，算法A在在输入为输入为I时的运行时间是：时的运行时间是：)I,n()I

5、,n(Tm1iii 最好、最坏和平均时间复杂度最好、最坏和平均时间复杂度最好时间复杂度最好时间复杂度最坏时间复杂度最坏时间复杂度平均时间复杂度平均时间复杂度最有实际价值：最坏时间复杂度最有实际价值：最坏时间复杂度T(n,I)DT(n,I)|IminB(n)n )T(n,IDT(n,I)|ImaxW(n)*n nDI P(I)T(n,I)A(n)2.1.4 使用程序步分析算法使用程序步分析算法 事前分析事前分析（priori analysispriori analysis）与）与事后测试事后测试（post testingpost testing）一个一个程序步程序步（program steppr

6、ogram step）是指）是指在语法上或语义上有意义的程序段，在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实该程序段的执行时间必须与问题实例的规模无关。例的规模无关。例子例子 求数组元素累加之和的迭代程序求数组元素累加之和的迭代程序float Sum(float list,float Sum(float list,constconst intint n)n)float float tempsumtempsum=0.0;=0.0;count+;/count+;/针对赋值语句针对赋值语句 for(for(intint i i=0;=0;i in;n;i i+)+)count+;c

7、ount+;/针对针对forfor循环语句循环语句 tempsumtempsum+=list+=listi i;count+;count+;/针对赋值语句针对赋值语句 count+;/count+;/针对针对forfor的最后一次执行的最后一次执行 count+;count+;/针对针对returnreturn语句语句 return return tempsumtempsum;总程序步数：总程序步数：2n+3求数组元素累加之和的递归程序求数组元素累加之和的递归程序float RSum(float list,const int n)count+;/针对针对 if 条件条件 if(n)count+

8、;/针对针对 RSum 调用和调用和return语句语句 return RSum(list,n-1)+listn-1;count+;/针对针对return语句语句 return 0;设设RSumRSum（list,nlist,n）的程序步为）的程序步为T(nT(n)0 n 2)1T(n 0 n 2T(n)T(nT(n)=2+T(n-1)=2+2+T(n-2)=2+T(n-1)=2+2+T(n-2)=2 =2*3+T(n-3)3+T(n-3)=2 =2*n+T(0)n+T(0)=2 =2*n+2n+22.1.5 算法的空间复杂度算法的空间复杂度 一个算法的一个算法的空间复杂度空间复杂度（spac

9、e complexityspace complexity）是指算法运行所需的存储空间。是指算法运行所需的存储空间。程序运行所需的存储空间包括以下两部分：程序运行所需的存储空间包括以下两部分：固定空间需求固定空间需求（fixed space requirementfixed space requirement）这部分空间与所处理数据的大小和个数这部分空间与所处理数据的大小和个数 无关，与问题实例的特征无关。无关，与问题实例的特征无关。主要包括主要包括程序代码程序代码、常量常量、简单变量简单变量、定长成分的结构变量定长成分的结构变量所占空间。所占空间。2.1.5 算法的空间复杂度算法的空间复杂度可

10、变空间需求可变空间需求（variable space requirementvariable space requirement）这部分空间大小与算法在某次执行中处理的特定数据的这部分空间大小与算法在某次执行中处理的特定数据的规模有关。规模有关。包括包括数据元素所占的空间数据元素所占的空间和和算法执行算法执行 所需的额外空间所需的额外空间，如递归所需的栈，如递归所需的栈 空间。空间。2.2 渐近表示法 2.2.1 大大O记号记号(渐近上界渐近上界)定义定义2-1 2-1 设函数设函数f(nf(n)和和g(ng(n)是定义在非负整数集合上的是定义在非负整数集合上的正函数，如果存在两个正常数正函数

11、，如果存在两个正常数c c和和n n0 0，使得当，使得当nnnn0 0时，有时，有f(n)cg(nf(n)cg(n)，则记做，则记做f(nf(n)=)=O(g(nO(g(n)称为大称为大O O记号（记号（big Oh notationbig Oh notation）。）。f(n)=2n+3=O(n)当当n3时，时，2n+33n，所以，可选，所以，可选c=3，n0=3。对于。对于nn0，f(n)=2n+33n，所以，所以，f(n)=O(n)，即，即2n+3 O(n)。这意味着，当。这意味着，当n3时，时，程序程序2-1的程序步不会超过的程序步不会超过3n，2n+3=O(n)。f(n)=10n2

12、+4n+2=O(n2)对于对于n2时，有时，有10n2+4n+210n2+5n，并且，并且当当n5时，时，5nn2，因此，可选，因此，可选c=11,n0=5；对于对于nn0，f(n)=10n2+4n+211n2，所以，所以f(n)=O(n2)。f(n)=n！=O(nn)对于对于n1，有，有n(n 1)(n 2)1nn，因此，因此，可选可选c=1，n0=1。对于。对于nn0，f(n)=n！nn，所以，所以，f(n)=O(nn)。10n2+9 O(n)使用反证法，假定存在使用反证法，假定存在c和和n0，使得对于，使得对于nn0，10n2+9cn始终成立，那么有始终成立，那么有10n+9/nc，即即

13、nc/10 9/(10n)总成立。但此不等式不可能总成立。但此不等式不可能总成立，取总成立，取n=c/10+1时，该不等式便不再成时，该不等式便不再成立。立。定理定理2-12-1 如果如果f(nf(n)=)=a am mn nm m +a+am m 1 1n nm m 1 1+a+a1 1n+an+a0 0是是m m次多项式，次多项式，且且a am m0 0，则，则f(nf(n)=)=O(nO(nm m)。证明：证明：取取n n0 0=1=1，当，当nnnn0 0时，有时，有 f(nf(n)=)=a am mn nm m +a+am m 1 1n nm m 1 1 +a+a1 1n+an+a0

14、 0|a am m|n|nm m +|a+|am m 1 1|n|nm m 1 1+|a+|a1 1|n+|a|n+|a0 0|(|a(|am m|+|a|+|am m 1 1|/n+|/n+|a+|a1 1|/n|/nm m 1 1+|a+|a0 0|/n|/nm m)n)nm m (|a(|am m|+|a|+|am m 1 1|+|+|a+|a1 1|+|a|+|a0 0|)n|)nm m可取可取c=|ac=|am m|+|a|+|am m 1 1|+|+|a+|a1 1|+|a|+|a0 0|，定理得证。，定理得证。渐近时间复杂度渐近时间复杂度 使用大使用大O记号及下面定义的几种渐近表

15、示法记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为表示的算法时间复杂度，称为算法的渐近时间算法的渐近时间复杂度复杂度（asymptotic complexityasymptotic complexity）。）。只要适当选择只要适当选择关键操作关键操作，算法的渐近时间复杂，算法的渐近时间复杂度可以由关键操作的执行次数度可以由关键操作的执行次数 之和来计算。一般地，关键操作之和来计算。一般地，关键操作 的执行次数与问题的规模有关，的执行次数与问题的规模有关，是是n n的函数。的函数。【程序程序2-32-3】矩阵乘法矩阵乘法forfor（i=0;in;i+i=0;in;i+）/n+1/n+

16、1 for for（j=0;jn;j+j=0;jn;j+）/n(n+1)/n(n+1)cijcij=0;=0;/n/n2 2 for for（k=0;kn;k+k=0;km,nm,则则 n mod mn/2n mod mn/2mn/2时，有时，有n-mn-mn/2n/2，定理得证。，定理得证。两次迭代以后，余数最多是原始值的一半。两次迭代以后，余数最多是原始值的一半。欧几里德算法的时间复杂度为欧几里德算法的时间复杂度为 O(logn+logmO(logn+logm)。2.2.2 记号（渐近下界）定义定义2-2 2-2 设有函数设有函数f f(n n)和和g g(n n)是定义在非负整是定义在非

17、负整数集合上的正函数，如果存在两个正数集合上的正函数，如果存在两个正常数常数 c c和和n n0 0，使得当，使得当n nn n0 0时，有时，有f f(n n)c c g g(n n)，则记做，则记做 f f(n n)=)=(g g(n n)，称为称为 记号记号（omega notationomega notation）。）。f(n)=2n+3=(n)对所有对所有n，2n+32n，可选可选c=2，n0=0。对于对于nn0，f(n)=2n+32n，所以，所以，f(n)=(n)，即即2n+3(n)。f(n)=10n2+4n+2=(n2)对所有对所有n，10n2+4n+210n2，可选可选c=10

18、，n0=0。对于对于nn0，f(n)=10n2+4n+210n2，所所以，以，f(n)=(n2)。如果如果f(n)=amnm+am 1nm 1+a1n+a0是是m次多项式，且次多项式，且am0，则，则f(n)=(nm)。2.2.3 记号（紧渐近界）定义定义2-3 2-3 设有函数设有函数f f(n n)和和g g(n n)是定义在非负整数集是定义在非负整数集合上的正函数，如果存在正常数合上的正函数，如果存在正常数c c1 1，c c2 2和和n n0 0，使得当使得当n nn n0 0时，有时，有c c1 1g g(n n)f f(n n)c c2 2g g(n n)，则记做则记做 f f(n

19、 n)=)=(g g(n n)，称为称为 记号（记号（Theta notationTheta notation）。）。f(n)=2n+3=(n)，即，即2n+3(n)。f(n)=10n2+4n+2=(n2)。如果如果f(n)=amnm+am 1nm 1+a1n+a0是是m次多项式，且次多项式，且am0，则，则f(n)=(nm)。2.2.4 小o记号（非紧上界）定义定义2-4 2-4 f f(n n)=)=o(o(g g(n n)当且仅当当且仅当f f(n n)=)=O(g g(n n)且且f f(n n)(g g(n n)例例2-9 2-9 f f(n n)=2)=2n n+3=o(+3=o(

20、n n2 2)，即，即2 2n n+3+3 o(o(n n2 2)。33渐近记号包括：(1)：紧确界。相当于=(2)O：上界。相当于=(3)o：非紧的上界。相当于=(5)：非紧的下界。相当于2.2.5 算法按时间复杂度分类算法按时间复杂度分类 算法按计算时间分类算法按计算时间分类凡渐近时间复杂度有多项式时间限界的算法凡渐近时间复杂度有多项式时间限界的算法称做称做多项式时间算法多项式时间算法（polynomial time polynomial time algorithmalgorithm），而渐近时间复杂度为指数函数），而渐近时间复杂度为指数函数限界的算法称做限界的算法称做指数时间算法指数时

21、间算法（exponential time algorithmexponential time algorithm）。）。最常见的多项式时间算法的渐近时间复杂度最常见的多项式时间算法的渐近时间复杂度 O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)最常见的指数时间算法的渐近时间复杂度最常见的指数时间算法的渐近时间复杂度 O(2n)O(n！)O(nn)提高计算机速度，可以较大幅度提高计算机速度，可以较大幅度地增加具有线性或地增加具有线性或nlog n时间算法时间算法所能处理的问题的能力，但对指所能处理的问题的能力，但对指数时间算法的收效甚微。数时间算法的收效甚微。为提高程序运

22、行速度，选择一种为提高程序运行速度，选择一种更快的算法比换一台更快的机器更快的算法比换一台更快的机器奏效。奏效。算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：（1 1）for/while for/while 循环循环循环体内计算时间循环体内计算时间*循环次数；循环次数；（2 2）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间*所有循环次数；所有循环次数；（3 3）顺序语句）顺序语句各语句计算时间相加；各语句计算时间相加；（4 4）if-elseif-else语句语句ifif语句计算时间和语句计算时间和elseelse语句计算时间的较大者。语句计算时间的较大者。最优算法最优算法

23、 问题的计算时间下界为问题的计算时间下界为(f f(n n)，则计算时间复杂，则计算时间复杂性为性为O(f f(n n)的算法是最优算法。的算法是最优算法。例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为(n nloglogn n)，计，计算时间复杂性为算时间复杂性为O(n nloglogn n)的排序算法是最优算法。的排序算法是最优算法。堆排序堆排序、快速排序快速排序、归并排序归并排序算法是算法是 最优算法。最优算法。递归算法复杂性分析递归算法复杂性分析 int factorialfactorial(int n)if(n=0)return 1;else return n*fact

24、orial(n-1);02)1(02)(nnTnnT22)(nnT递推关系常用来分析递归算法。递推关系常用来分析递归算法。2.3 递推关系递推关系2.3.1 递推方程递推方程 递推方程递推方程（recurrence equationrecurrence equation）是自然）是自然数上一个函数数上一个函数T T(n n)，它使用一个或多个小于，它使用一个或多个小于n n时的值的等式或不等式来描述。递推方程时的值的等式或不等式来描述。递推方程也称为也称为递推关系或递推式递推关系或递推式。递推方程必须有一个递推方程必须有一个初始条件初始条件 （也称边界条件）。（也称边界条件）。逆序输出正整数的

25、各位数逆序输出正整数的各位数 【程序程序1-51-5】void void PrintDigit(unsignedPrintDigit(unsigned intint n)n)coutcoutn%10;=10)=10)PrintDigit(n/10);PrintDigit(n/10);/以逆序输出前以逆序输出前k k-1-1位数位数 例例2-102-10 程序程序1-51-5的时间分析的时间分析 设设n n=d d1 1d d2 2d dk k是是k k位数，当位数，当k k=1=1时，只执行时，只执行coutcout语句和语句和ifif判定语句；当判定语句；当n n至少是至少是2 2位数位数（

26、k k1 1）时，除了执行这两个操作外，还需）时，除了执行这两个操作外，还需执行递归函数调用执行递归函数调用PrintDigit(PrintDigit(n n/10)/10)，n n/10/10 是是k k 1 1位数位数 。1 k2)1T(k1 k 2T(k)T(k)=2k=(k)计算递推式的方法：计算递推式的方法：迭代方法（迭代方法（iteratingiterating）替换方法（替换方法（substitutionsubstitution）主方法（主方法（master methodmaster method）2.3.3 迭代方法迭代方法 迭代方法迭代方法的思想是扩展递推式，将递推式先转的思

27、想是扩展递推式，将递推式先转换成一个和式，然后计算该和式，得到渐近复换成一个和式，然后计算该和式，得到渐近复杂度。杂度。例例2-122-12 使用迭代方法分析程序使用迭代方法分析程序1-61-6。函数函数HanoiHanoi中两次调用自身，函数调用中两次调用自身，函数调用使用的实在参数均为使用的实在参数均为n n 1 1，函数，函数MoveMove所需时间具有常数界所需时间具有常数界(1)(1)，可以将其，可以将其视为一个程序步，于是有：视为一个程序步，于是有：1 n 1)1T(n21 n 1T(n)47void Hanoi(int n,tower x,tower y,tower z)/将将x

28、上部的上部的n个圆盘移到个圆盘移到y上，顺序不变。上，顺序不变。if(n)Hanoi(n-1,x,z,y);Move(n,x,y);Hanoi(n-1,z,y,x);扩展并计算此递推式：扩展并计算此递推式：T(nT(n)=2T(n)=2T(n 1)+1 1)+1 =2(2T(n 2)+1)+1 =22T(n 2)+2+1=2=23 3T(n T(n 3)+2 3)+22 2+2+1+2+1=2=2n n 1 1T(1)+2T(1)+22 2+2+1+2+1=2=2n n 1 1+2+22 2+2+1=2+2+1=2n n 1 1我们应该谨慎使用递归算法，因为他们我们应该谨慎使用递归算法，因为他

29、们的简洁可能会掩盖他们的低效率。的简洁可能会掩盖他们的低效率。2.3.2 替换方法替换方法 替换方法替换方法要求首先猜测递推式的解，然后要求首先猜测递推式的解，然后用归纳法证明。用归纳法证明。例例2-112-11 使用替换方法分析使用替换方法分析程序程序1-61-6。汉诺塔问题汉诺塔问题enum tower A=X,B=Y,C=Z;void Move(int n,tower x,tower y)cout The disk n is moved from char(x)to top of tower char(y)endl;void Hanoi(int n,tower x,tower y,tow

30、er z)if(n)Hanoi(n-1,x,z,y);Move(n,x,y);Hanoi(n-1,z,y,x);2.3.2 替换方法替换方法可以先对以下这些小的示例进行计算：可以先对以下这些小的示例进行计算：T T(3)=7=2(3)=7=23 3 1 1；T T(4)=15=2(4)=15=24 4 1 1；T T(5)=31=2(5)=31=25 5 1 1；T T(6)=63=2(6)=63=26 6 1 1看起来，似乎看起来，似乎T T(n n)=2)=2n n 1 1，n n11。使用使用递归树递归树（recursion treerecursion tree）可以形象）可以形象地看到

31、递推式的迭代过程。地看到递推式的迭代过程。例例2-13 T T(n n)=2)=2T T(n n/2)+/2)+n n的递归树的递归树 例例2-14 2-14 T T(n n)=)=T T(n n/3)+/3)+T(T(2 2n n/3)+/3)+n n的递归树的递归树2.3.4 主方法主方法 主方法主方法在递归算法分析中，常需要求解如下形式的递在递归算法分析中，常需要求解如下形式的递推式：推式：T T(n n)=)=aTaT(n n/b b)+)+f f(n n)式中，式中，a a11和和b b1 1是常数，是常数，f f(n n)是是一个渐近正函数，一个渐近正函数，n n/b b指指 n

32、n/b b 或或 n n/b b。求解这类递推式的方法称为主方法。求解这类递推式的方法称为主方法。定理定理2-5 （主定理）设（主定理）设a1a1和和b b1 1为常数，为常数，f(nf(n)是一个函数，是一个函数，T(nT(n)由下面的递推式定义由下面的递推式定义T(nT(n)=)=aT(n/baT(n/b)+)+f(nf(n)式中，式中，n/bn/b指指 n/bn/b 或或 n/bn/b，则，则T(nT(n)有如下的渐有如下的渐近界：近界：（1 1）若对某常数）若对某常数0 0，有，有f(nf(n)=)=O()()，则，则T(nT(n)=()()；ablognablogn例2-18 T(n)=2T(n/2)+nlogn 由于a=2,b=2,f(n)=nlogn和 =n。看起来似乎属于主定理情况（3），但事实上不是。因为f(n)只是渐近大于n，但并不是多项式大于n。f(n)与 的比值是log n，对于任何正数 ，log n渐近小于n，所以，此例不能运用主定理。ablognablogn课堂练习习题2 2-8 2-17 2-19