算法2_算法分析基础

1、第第2章章 算法分析基础算法分析基础u学习要点：学习要点：u掌握算法分析中的掌握算法分析中的算法复杂度概念算法复杂度概念时间时间复杂度、复杂度、空间空间复杂度复杂度最好最好、最坏最坏和和平均平均情况时间复杂度情况时间复杂度u掌握掌握算法分析的渐近表示法算法分析的渐近表示法u掌握用掌握用C+语言描述算法的方法语言描述算法的方法u章节内容：章节内容：u2.1 算法复杂度算法复杂度u2.2 渐近表示法渐近表示法u2.3 递推关系（课外阅读）递推关系（课外阅读）2.1 算法复杂度算法复杂度好算法的好算法的4个重要特征：个重要特征：uCorrectness正确性正确性注意区分注意区分“正确性正确性”和和

2、“健壮性健壮性”的概念：的概念：算法算法正确性正确性在合法的输入下，算法应实现预先规定的功能和计算精度要求。在合法的输入下，算法应实现预先规定的功能和计算精度要求。程序程序健壮性健壮性当输入不合法的数据时，程序应能做适当处理而不至于引起严当输入不合法的数据时，程序应能做适当处理而不至于引起严重后果。重后果。正确性正确性和和健壮性健壮性互相补充。互相补充。程序程序可靠性可靠性在正常情况下能正确地工作，在异常情况下也能做出适当处理。在正常情况下能正确地工作，在异常情况下也能做出适当处理。2.1 算法复杂度算法复杂度好算法的好算法的4个重要特征：个重要特征：uCorrectness正确性正确性uSi

3、mplicity, clarity简明性简明性遗憾的是，简单的算法不一定高效遗憾的是，简单的算法不一定高效思路清晰、层次分明、容易理解、利于编码和调试。思路清晰、层次分明、容易理解、利于编码和调试。2.1 算法复杂度算法复杂度好算法的好算法的4个重要特征：个重要特征：uCorrectness正确性正确性uSimplicity, clarity简明性简明性uAmount of time/space used效率效率执行算法所需的时间和存储空间执行算法所需的时间和存储空间算法设计者常常需要在算法的算法设计者常常需要在算法的简明简明性性和和效率效率之间作出谨慎的选择之间作出谨慎的选择2.1 算法复杂

4、度算法复杂度好算法的好算法的4个重要特征：个重要特征：uCorrectness正确性正确性uSimplicity, clarity简明性简明性uAmount of time/space used效率效率uOptimality最优性最优性算法执行时间达到求解该类问题所需算法执行时间达到求解该类问题所需时间的下界时间的下界。与所求解问题自身的复杂程度有与所求解问题自身的复杂程度有关。关。uFor problem P, the algorithm A does at most WA(n) steps in the worst case (upper bound)uF is a lower bound

5、 for a class of algorithm. (lower bound) uIf WA=F, then A is optimal.Definition of the optimal algorithm（最优算法）（最优算法）means that: For any algorithm in the class, and any input of size n, there is some input of size n for which the algorithm must perform at least F(n) basic operations.又如：又如：可证可证排序问题的排序

6、问题的时间复杂度下界时间复杂度下界为为 (nlogn)。则则最坏时间复杂性为最坏时间复杂性为O(nlogn)的排序算法是的排序算法是最优算法最优算法。因此：因此：堆排序堆排序算法和算法和两路合并排序两路合并排序算法都是算法都是最优算法最优算法。例如例如:FindMax(int L) /求求n个元素中的最大元素个元素中的最大元素 int max=L0; int i=1; while(in) if (maxLi) max=Li; i=i+1; 最优算法最优算法影响影响程序程序运行时间的因素运行时间的因素u程序所依赖的程序所依赖的算法算法u问题规模问题规模和和输入数据输入数据u计算机系统计算机系统性

7、能性能根本的、起决定作用的根本的、起决定作用的数值大小和状态数值大小和状态硬件系统性能（硬件系统性能（CPU速度）和软件系统性能（操作系统、编译器）速度）和软件系统性能（操作系统、编译器）输入、输出输入、输出运行一个算法所需的运行一个算法所需的时间时间和和空间空间资源的量。资源的量。u算法的算法的时间时间复杂性（复杂性（Time Complexity）T(n)u算法的算法的空间空间复杂性（复杂性（Space Complexity）S(n) 其中其中n是问题的规模（输入大小）是问题的规模（输入大小）算法复杂度算法复杂度How to Measure?Machine independentLangu

8、age independentProgramming style independentImplementation independentu算法的时间复杂度算法的时间复杂度算法运行所需的时间算法运行所需的时间u最好最好、最坏最坏和和平均平均时间复杂度时间复杂度( (不考虑计算机因素对算法分析的影响）不考虑计算机因素对算法分析的影响）最好最好情况（情况（出现概率较大时出现概率较大时分析）分析）最差最差情况（情况（实时系统实时系统）平均平均情况（情况（已知已知输入数据是如何输入数据是如何分布分布的，通常的，通常假设假设等概率分布等概率分布）算法的时间复杂度算法的时间复杂度（1 1）最好情况最好情

9、况下的时间复杂性：下的时间复杂性：B(n) = Tmin(n) = min T(n,I) | IDn （2 2）最坏情况最坏情况下的时间复杂性：下的时间复杂性：W(n) = Tmax(n) = max T(n,I) | IDn （3 3）平均情况平均情况下的时间复杂性：下的时间复杂性：A(n) = Tavg(n) =I:I:问题规模为问题规模为n n的实例。的实例。D Dn n : :规模为规模为n n的所有合法输入的集合。的所有合法输入的集合。p(Ip(I):):实例实例I I出现的概率。出现的概率。I Dn p(I)T(n,I)算法的算法的空间空间复杂度复杂度u算法的空间复杂度算法的空间复

10、杂度 算法运行所需的存储空间算法运行所需的存储空间固定固定空间需求空间需求与所处理数据的大小和个数无关，即与所处理数据的大小和个数无关，即与问题实例的特征无关与问题实例的特征无关。（包括：程序代码、常量、简单变量、定长成分的结构变量（包括：程序代码、常量、简单变量、定长成分的结构变量所占的空间）所占的空间）可变可变空间需求空间需求与算法执行过程中处理的与算法执行过程中处理的特定数据的规模有关。特定数据的规模有关。（如：数据元素所占的空间，算法执行所需的额外空间（如：数据元素所占的空间，算法执行所需的额外空间如如递归算法所需系统栈空间）递归算法所需系统栈空间）通过程序步来分析算法的时间复杂度通过

11、程序步来分析算法的时间复杂度求数组元素累加之和的求数组元素累加之和的迭代迭代程序：程序：(P20 程序程序2-1)float Sum(float list,const int n) float tempsum=0.0; /1 for (int i=0;in;i+)/n+1 tempsum+=listi; /n return tempsum;/1程序总步数为：程序总步数为：2n+3求数组元素累加之和的求数组元素累加之和的递归递归程序：程序：(P21 程序程序2-2)float RSum(float list,const int n) if (n)/1 return RSum(list,n-1)+

12、listn-1;/1 return 0;/120( )(1)20nT nT nn程序总步数为：程序总步数为：2n+2但但递归调用递归调用引起的循环计算和使用引起的循环计算和使用for语句语句的循环计算的循环计算所需的开销是不同的所需的开销是不同的。递。递归需要耗费更多的时间和空间资源。归需要耗费更多的时间和空间资源。可见：可见：程序步数并不能确切反映程序运行的实际时间。程序步数并不能确切反映程序运行的实际时间。2.2 渐近表示法渐近表示法u 程序步的精确计算是困难的，且程序步并不能确切反映程序运行的实际程序步的精确计算是困难的，且程序步并不能确切反映程序运行的实际时间。时间。u 因此引入因此引

13、入渐近时间复杂度渐近时间复杂度, ,使用程序步在数量级上估计一个算法的执行时使用程序步在数量级上估计一个算法的执行时间，从而实现算法的事前分析。间，从而实现算法的事前分析。u 在在数学上数学上，算法的渐近复杂度，算法的渐近复杂度t(n)是是T(n) 的的渐近表达式渐近表达式，是，是T(n)略去低阶略去低阶项留下的主项项留下的主项，它比，它比T(n) 简单。简单。例如例如: T(n)=3n2+4nlogn+7 与与t(n)= 3n2 当当n时，有时，有(T(n)-t(n)/T(n) 0。渐近分析的记号：渐近分析的记号：O、o、 在下面的讨论中，对所有在下面的讨论中，对所有n，f(n) 0，g(n

14、) 0。 （1 1）渐近上界记号渐近上界记号O如果存在正常数如果存在正常数c和自然数和自然数n0，使得当使得当n n0时时有有f(n) cg(n)，则称函数则称函数f(n)当当n充分大时有上界，且充分大时有上界，且g(n)是它的一个上界是它的一个上界，记，记做做f(n)=O(g(n) 。即。即f(n)的阶不高于的阶不高于g(n)的阶的阶。 上界上界记号记号O举例：举例：uC0=O(1)f(n)=C0为非零常数，取为非零常数，取c=c0u100n+6=O(n)取取c=101, n0=6u6*2n+n2=O(n2)取取c=7, n0=4u3log n+2*n+n2=O(n2)取取c=6, n0=1

15、证明证明 见见P22 例如：程序例如：程序2-1float Sum(float list,const int n) float tempsum=0.0;/1 for (int i=0;in;i+)/n+1 tempsum+=listi;/n return tempsum;/1关键操作关键操作通常是位于算法最内层循环的程序步（或语句），通常是位于算法最内层循环的程序步（或语句），是算法中执行次数最多的操作（程序步）是算法中执行次数最多的操作（程序步） 。关键操作关键操作通常是位于算法最内层循环的程序步（或语句），通常是位于算法最内层循环的程序步（或语句），是算法中执行次数最多的操作（程序步）是算

16、法中执行次数最多的操作（程序步） 。例如：程序例如：程序2-3 矩阵乘法矩阵乘法for (i=0;in;i+)/n+1 for (j=0;jn;j+)/n(n+1) cij=0;/n2for (k=0;kn) Swap(m,n);while (m0) int c=n%m; n=m; m=c;return n;定理定理2-2 如果如果nm ，则则n mod m 0都存在正整数都存在正整数n0 0，使得当，使得当n n0时有时有f(n)cg(n) （等价于（等价于:n时，时，f(n) / g(n) 0），则称，则称函数函数f(n)当当n充分大时的阶比充分大时的阶比g(n)低低，记做，记做f(n)=

17、o(g(n)。（5 5）非紧下界记号非紧下界记号 如果对于任何正常数如果对于任何正常数c0都存在正整数都存在正整数n0 0，使得当，使得当n n0时有时有f(n)cg(n) （等价于（等价于n时，时，f(n)/g(n)），则称），则称函数函数f(n)当当n充分大时的阶比充分大时的阶比g(n)高高，记做，记做f(n) (g(n)。f(n)= o(g(n) g(n)= (f(n) 渐近分析中函数比较渐近分析中函数比较uf(n)= O(g(n) f(n) g(n);uf(n)= (g(n) f(n) g(n);uf(n)= (g(n) f(n) = g(n);uf(n)= o(g(n) f(n) g

18、(n).证明：证明：对于对于任意任意f1(n) O(f(n) ，存在正常数，存在正常数c1和自然数和自然数n1，使得，使得对所有对所有n n1，有，有f1(n) c1f(n) 。类似地，对于类似地，对于任意任意g1(n) O(g(n) ，存在正常数，存在正常数c2和自然和自然数数n2，使得对所有，使得对所有n n2，有，有g1(n) c2g(n) 。令令c3=maxc1, c2， n3 =maxn1, n2，则对所有的则对所有的 n n3，有，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n) = c3(f(n) + g(n) 2c3 maxf(n),g

19、(n) = O( maxf(n),g(n) ) 思考题：证明思考题：证明O(f(n)+O(g(nO(f(n)+O(g(n) ) = O(maxf(n),g(n O(maxf(n),g(n) 顺序搜索算法顺序搜索算法templateint seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1;时间复杂度综合分析（例时间复杂度综合分析（例1）（1）最坏情况最坏情况下：下：Tmax(n) = max T(I) | size(I)=n =O(n)（2）最好情况最好情况下：下：Tmin(n)

20、= min T(I) | size(I)=n =O(1)（3）平均情况平均情况下，假设：下，假设：u搜索成功的概率为搜索成功的概率为p (0 p 1)；u在数组的每个位置在数组的每个位置i (0 in)搜索成功的概率相同，均为搜索成功的概率相同，均为 p/n。nIsizeavgITIpnT)()()()(pnnpnnpnpnp1321)1 (2) 1(11pnnppninpni非递归算法的时间复杂度分析法则：非递归算法的时间复杂度分析法则：（1 1）for / while for / while 循环循环循环体内计算时间循环体内计算时间* *循环次数；循环次数；（2 2）嵌套循环）嵌套循环循环

21、体内计算时间循环体内计算时间* *所有循环次数；所有循环次数；（3 3）顺序语句）顺序语句各语句计算时间相加；各语句计算时间相加；（4 4）if-elseif-else语句语句ifif语句计算时间和语句计算时间和elseelse语句计算时间的较大者。语句计算时间的较大者。templatevoid insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 & ajkey ) / c4sum of ti aj+1=aj; / c5 sum of (ti-1) j-; / c6 sum of (ti-1) a

22、j+1=key; / c7 n-1 时间复杂度综合分析（例时间复杂度综合分析（例2）u 在最好情况下，在最好情况下，ti=1, for 1 i n;u 在最坏情况下，在最坏情况下，ti i+1, for 1 i n;1111234567111( )(1)(1)(1)(1)(1)nnniiiiiiT nc nc nc nctctctc n) 1() 1() 1() 1()(74321minncncncncncnT123472347()()( )ccccc nccccO n1112) 1() 1(ninni112) 1(ninnimax1234567(1)(1)(1)( )(1)(1)1(1)22

23、2n nn nn nTnc nc nc ncccc n对于输入数据对于输入数据ai=n-i, i=0,1,n-1，算法，算法insertion_sort 达到其最坏情形。达到其最坏情形。while首句：首句：while循环体：循环体：2456456123723472()22()ccccccnccccnccccO n算法按时间复杂度分类算法按时间复杂度分类u多项式时间算法多项式时间算法渐近时间复杂度有多项式时间限界的算法渐近时间复杂度有多项式时间限界的算法O(1) O(logn) O(n) O(nlogn) O(n2) O(n3)u指数时间算法指数时间算法渐近时间复杂度为指数函数限界的算法渐近时

24、间复杂度为指数函数限界的算法O(2n) O(n!) 9 ? 100:200; 等价于： if (x9) y=100; else y=200;u1.3 switch语句：switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; （2）迭代语句：）迭代语句：u 2.1 for 循环： for (init;condition;inc) statement;u 2.2 while 循环：while (condition) s

25、tatement;u 2.3 do-while 循环： do statement; while (condition); （3）跳转语句：）跳转语句：u 3.1 return语句：return expression;u 3.2 goto语句： goto label; label:（4）函数：）函数：u 例： return-type function name(para-list) body of the function int max(int x,int y) return xy?x:y; （5）模板）模板template ：template Type max(Type x,Type y)

26、return xy?x:y; int i=max(1,2)；double x=max(1.0,2.0)；（6）动态存储分配：）动态存储分配：u 6.1 运算符运算符new ：运算符运算符new用于动态存储分配，返回一个指向所分配空间的指针。用于动态存储分配，返回一个指向所分配空间的指针。例：例：int y；y=new int； y=10；也可将上述各语句作适当合并如下：也可将上述各语句作适当合并如下：int y=new int； y=10；或或 int y=new int(10)；或或 int y；y=new int(10)；为了在运行时创建一个为了在运行时创建一个大小可动态变化大小可动态变化

27、的一维浮点数组的一维浮点数组x，可先将，可先将x声明为一个声明为一个float类型的指针。然后用类型的指针。然后用new为数组动态地分配存储空间。为数组动态地分配存储空间。例：float p=new floatn；创建一个大小为创建一个大小为n的一维浮点数组。运算符的一维浮点数组。运算符new分配分配n个浮点数所需的个浮点数所需的空间，并返回指向第一个浮点数的指针。空间，并返回指向第一个浮点数的指针。然后可用然后可用p0，p1，pn-1来访问每个数组元素。来访问每个数组元素。u6.2 一维数组一维数组 ：u 例：例：int n=5;int *p=new intn;for (int i=0;in

28、;i+)pi=i;coutpi;当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运算符算符delete来释放由来释放由new分配的空间。分配的空间。例：delete y；delete x；分别释放分配给分别释放分配给 y的空间和分配给一维数组的空间和分配给一维数组x的空间。的空间。u6.3 运算符运算符delete delete ：创建类型为创建类型为Type的动态工作数组，这个数组有的动态工作数组，这个数组有rows行和行和cols列。列。template void Make2DArray(Type* &x,int row

29、s, int cols) x=new Type* rows; for (int i=0;irows;i+) xi=new Typecols;u6.4 动态二维数组动态二维数组 ：u 当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在的空间。首先释放在for循环中为每一行所分配的空间。然后释放为循环中为每一行所分配的空间。然后释放为行指针分配的空间。行指针分配的空间。template void Delete2DArray(Type* &x,int rows) for (int i=0;irows;i+) de

30、lete xi; delete x; x=0;释放空间后将释放空间后将x置为置为0，以防，以防继续访问已被释放的空间。继续访问已被释放的空间。u作业：作业：P33 2-8( (仅需给出划线语句执行次数和渐近时间复杂度）仅需给出划线语句执行次数和渐近时间复杂度） 2-10 2-13(更正）更正）关键：根据递归过程建立递推关系式，然后求解关键：根据递归过程建立递推关系式，然后求解这个递推关系式。这个递推关系式。1. 猜测技术猜测技术:对对递推关系式估计一个上限，然后（用数学归递推关系式估计一个上限，然后（用数学归纳法）证明它正确。纳法）证明它正确。附录：递归算法附录：递归算法2. 扩展递归技术扩展

31、递归技术 15)2(217)(2nnnTnnT222112222225)2(52)2(52) 1 (25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk )(2nO 。3. 通用分治递推式通用分治递推式大小为大小为n的原问题分成若干个大小为的原问题分成若干个大小为n/b的子问题，的子问题，其中其中a个子问题需要求解，而个子问题需要求解，而cnk是合并各个子问题是合并各个子问题的解需要的工作量。的解需要的工作量。 1)(1)(ncnbnaTncnTk kkkbkkabanObannObanOnTb)()log()()(log附录：渐近

32、分析记号的若干性质附录：渐近分析记号的若干性质（1）传递性：）传递性：u f(n)= (g(n)，g(n)= (h(n) f(n)= (h(n)；u f(n)= O(g(n)，g(n)= O(h(n) f(n)= O (h(n)；u f(n)= (g(n)，g(n)= (h(n) f(n)= (h(n)；u f(n)= o(g(n)，g(n)= o(h(n) f(n)= o(h(n)；u f(n)= (g(n)，g(n)= (h(n) f(n)= (h(n)；（2）反身性：）反身性：u f(n)= (f(n)；u f(n)= O(f(n)；u f(n)= (f(n).（3）对称性：）对称性：u

33、 f(n)= (g(n) g(n)= (f(n) .（4）互对称性：）互对称性：u f(n)= O(g(n) g(n)= (f(n) ；u f(n)= o(g(n) g(n)= (f(n) ；（5）算术运算：）算术运算：u O(f(n)+O(g(n) = O(maxf(n),g(n) ；u O(f(n)+O(g(n) = O(f(n)+g(n) ；u O(f(n)*O(g(n) = O(f(n)*g(n) ；u O(cf(n) = O(f(n) ；其中；其中c是一个正的常数；是一个正的常数； u 如果如果g(n)= O(f(n) 则则O(f(n)+O(g(n) = O(f(n) 。u f=O(f)。取整函数取整函数u x ：不大于：不大于x的最大整数；的最大整数；u x ：不小于：不小于x的最小整数。的最小整数。 u x-1 x x x 0）u (am)n = amn ; u (am)n = (an)m ; u aman = am+n ;u a1 an为为单调递增函数单调递增函数;u a1 nb = o(an)u