第1章_基础算法设计与分析

1、1东北大学软件学院东北大学软件学院算法设计与分析算法设计与分析The Analysis and Design of Algorithms2与数据结构的区别：与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同的设计技术的适用性和效率。和效率；算法关心不同的设计技术的适用性和效率。考虑问题的高度：数据结构关心的是解具体问题，算法不仅于此，考虑问题的高度：数据结构关心的是解具体问题，算法不仅于此，它提供一种解决问题的通用方法。它提供一种解决问题的通用方法。与其他课程的关系与其他课程的关系高级程序设计语

2、言（高级程序设计语言（C, C+）数据结构数据结构算法设计算法设计与与分析分析数据库系统，编译方法，操作系统数据库系统，编译方法，操作系统授人以鱼，不如授人以渔授人以鱼，不如授人以渔Learning such techniques is akin to learning to fish as opposed to being given a fish caught by somebody else.3About Algorithml课程主要讨论和介绍计算机算法的复杂性理论，课程主要讨论和介绍计算机算法的复杂性理论，主要介绍计算机科学及应用领域常见的有代表主要介绍计算机科学及应用领域常见的有代表

3、性的非数值算法及算法设计的若干重要方法，性的非数值算法及算法设计的若干重要方法，同时，介绍算法分析的基本知识。同时，介绍算法分析的基本知识。l你可以学到：算法设计方法、分析基本技术、你可以学到：算法设计方法、分析基本技术、锻炼逻辑思维。锻炼逻辑思维。l先修课程：离散数学、数据结构、高级程序设先修课程：离散数学、数据结构、高级程序设计语言。计语言。 有两种思想，象珠宝商放在天鹅绒上的宝石一样熠熠生辉，一个是微积分，有两种思想，象珠宝商放在天鹅绒上的宝石一样熠熠生辉，一个是微积分，另一个就是算法。微积分以及在微积分基础上建立起来的数学分析体系造就了现另一个就是算法。微积分以及在微积分基础上建立起来

4、的数学分析体系造就了现代科学，而算法则早就了现代世界。代科学，而算法则早就了现代世界。 David Berlinski，20004课程内容课程内容l算法概述（算法概述（Foundation）l递归与分治策略（递归与分治策略（Divide and Conquer）l动态规划（动态规划（Dynamic Programming）l贪心算法（贪心算法（Greedy Algorithm）l回溯法（回溯法（Back Tracking）l分支限界法（分支限界法（Branch and Bound ）5计算机算法设计与分析计算机算法设计与分析(第第3版版).王晓东王晓东.电子工业出版社电子工业出版社.2007年

5、年5月月Teaching Material： 6References1Introduction to Algorithms, Second Edition. Thomas H. Cormen. The MIT Press. 2 算法设计与分析基础算法设计与分析基础. （美）（美）Anany Levitin著，潘彦译著，潘彦译. 北京：清华北京：清华大学出版社大学出版社. 2004年年6月月7第第1章章 算法概述算法概述 1.1 算法与程序算法与程序 1.2 算法复杂性分析初步算法复杂性分析初步8本章教学要求本章教学要求l理解算法与程序的概念，二者区别与联系理解算法与程序的概念，二者区别与联系l

6、掌握算法复杂性的渐近性态的数学表述掌握算法复杂性的渐近性态的数学表述l掌握描述算法的方法掌握描述算法的方法重点重点l理解算法与程序理解算法与程序l算法复杂性的渐近性态的数学表述算法复杂性的渐近性态的数学表述l算法表示方法算法表示方法难点难点l算法复杂性的渐进性态的数学表述算法复杂性的渐进性态的数学表述9lWhats Algorithm? 算法是一系列解决问题的算法是一系列解决问题的清晰清晰指令，也就是说，能够对指令，也就是说，能够对一定规范的一定规范的输入输入，在，在有限时间有限时间内获得所要求的内获得所要求的输出输出。1.1 算法与程序算法与程序10What is an algorithm?

7、bInputbvalid inputs are clearly specifiedbOutputbcan be proved to produce the correct output given a valid inputbDefinitenessbrigorously and unambiguously specifiedbFinitenessbterminates after a finite number of stepsbEffectivenessbsteps are sufficiently simple and basic11算法的五个重要特征算法的五个重要特征l输入输入 有有零

8、个或多个零个或多个由外部提供的量作为算法的输入由外部提供的量作为算法的输入.l输出输出 算法产生算法产生至少一个量至少一个量作为输出作为输出.l确定性确定性 组成算法的每条指令是清晰的组成算法的每条指令是清晰的,无歧义的无歧义的.l有限性有限性 在执行了有穷步骤后运算终止在执行了有穷步骤后运算终止.l可行性可行性 运算都是基本运算，原理上能在有限时间内完成运算都是基本运算，原理上能在有限时间内完成.1.1 算法与程序算法与程序12Example of computational problem: sortinglStatement of problem:lInput: A sequence o

9、f n numbers lOutput: A reordering of the input sequence so that ai aj whenever i jlInstance: The sequence lAlgorithms:lSelection sortlInsertion sortlMerge sortl(many others)13一般求一般求d=gcd(m,n)的过程用自然语言可以描述如下：的过程用自然语言可以描述如下： (1) 找出找出m的素因子的素因子; (2) 找出找出n的素因子的素因子; (3) 找出找出m，n的公共的素因子的公共的素因子; (4) 计算所有公共素因子

10、的乘积，结果即为计算所有公共素因子的乘积，结果即为m，n的最大的最大公约数。公约数。 这样的过程能称之为算法吗？这样的过程能称之为算法吗？求两个数的最大公约数求两个数的最大公约数1.1 算法与程序算法与程序例例1114计算计算gcd(m,n)的连续整数检测算法的连续整数检测算法第一步第一步：将：将minm,n的值赋给的值赋给t。第二步第二步：m除以除以t，如果余数为，如果余数为0，进入第三步；，进入第三步；否则进入第四步。否则进入第四步。第三步第三步：n除以除以t，如果余数为，如果余数为0，返回，返回t的值作为的值作为结果；否则，进入第四步。结果；否则，进入第四步。第四步第四步：把：把t的值减

11、的值减1。返回第二步。返回第二步。例：对于例：对于60和和24这两个数，该算法会先尝试这两个数，该算法会先尝试24，然后是，然后是23，这样一直尝试到，这样一直尝试到12，算法结束。，算法结束。当它的一个输入为当它的一个输入为0时，计算出来的结果是错误的。时，计算出来的结果是错误的。1.1 算法与程序算法与程序15欧几里德算法欧几里德算法lgcd ( m, n ) = gcd ( n, m mod n )lgcd ( 24, 18 ) = gcd ( 18, 6 ) = gcd ( 6, 0 ) = 6l输入输入 正整数正整数m和和n 输出输出 m和和n的最大公因子的最大公因子1.如果如果n

12、= 0, 计算停止返回计算停止返回m, m即为结果；否则继续即为结果；否则继续2。2.记记r为为m除以除以n的余数，即的余数，即r=m mod n。3.把把n赋值给赋值给m，把，把r赋值给赋值给n，继续，继续1。l伪代码如下：伪代码如下： Euclid(m, n) while( n!= 0) r = m mod n; m = n; n = r; 验证辗转相除法是否符合算法的五个要求验证辗转相除法是否符合算法的五个要求?1.1 算法与程序算法与程序Beginn=0?r=m mod nm=nn=rendNY16Some Well-known Computational ProblemslSorti

13、nglSearchinglShortest paths in a graphlMinimum spanning treelTraveling salesman problemlKnapsack problemlChesslTowers of HanoilProgram termination17程序程序l程序程序= =数据结构数据结构+ +算法算法l可以不满足有限性可以不满足有限性l程序性能程序性能( (program performance)：指运行一指运行一个程序所需要的内存大小和时间。个程序所需要的内存大小和时间。算法的描述算法的描述 自然语言方式、表格方式等自然语言方式、表格方式等1.

14、1 算法与程序算法与程序18Basic Issues Related to AlgorithmslHow to design algorithmslHow to express algorithmslProving correctnesslEfficiencylTheoretical analysislEmpirical analysislOptimality19Algorithm design strategieslBrute forcelDivide and conquerlDecrease and conquerlTransform and conquerlGreedy approach

15、lDynamic programminglBacktracking and Branch & BoundlSpace and time tradeoffs20Analysis of AlgorithmslHow good is the algorithm?lCorrectnesslTime efficiencylSpace efficiencylDoes there exist a better algorithm?lLower boundslOptimality21l算法的复杂性算法的复杂性 l设计算法追求的目标设计算法追求的目标l选用算法的准则选用算法的准则 1.2 算法分析初步

16、Analysis of Algorithms时间复杂性时间复杂性 需要时间资源的量需要时间资源的量空间复杂性空间复杂性 需要的空间资源的量需要的空间资源的量设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法选择已有算法中复杂性最低者选择已有算法中复杂性最低者不是所有能计算的都有价值，不是所有有价值的都能被计算。不是所有能计算的都有价值，不是所有有价值的都能被计算。 阿尔伯特阿尔伯特. . 爱因斯坦爱因斯坦221. 1. 多用户系统中运行时，需指多用户系统中运行时，需指明分配给该程序的内存大小。明分配给该程序的内存大小。2. 2. 想提前知道是否有足够可用想提前知道是否有足够可用的内存来运行该

17、程序。的内存来运行该程序。3. 3. 一个问题可能有若干个内存一个问题可能有若干个内存需求各不相同的解决方案，从需求各不相同的解决方案，从中择取。中择取。4. 4. 利用空间复杂性来估算一个利用空间复杂性来估算一个程序所能解决的问题的最大规程序所能解决的问题的最大规模。模。考虑程序的空间复杂性的理由考虑程序的空间复杂性的理由1.2 算法分析初步算法分析初步231.有些计算机需要用户提供程序运行有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，时间的上限，一旦达到这个上限，程序将被强制结束。程序将被强制结束。2.正在开发的程序可能需要提供一个正在开发的程序可能需要提供一个满意的实时响应

18、。满意的实时响应。程序的时间复杂性：运行完该程序所需要的时间。程序的时间复杂性：运行完该程序所需要的时间。为什么要考虑时间复杂性？为什么要考虑时间复杂性？1.2 算法分析初步算法分析初步24一、空间复杂性一、空间复杂性程序所需要的空间主要由程序所需要的空间主要由指令空间指令空间，数据空间数据空间，环境栈空间环境栈空间构成：构成：u指令空间（指令空间（instruction space）：用来存储经过）：用来存储经过编译之后的程序指令所需的空间。编译之后的程序指令所需的空间。u把程序编译成机器代码的编译器；把程序编译成机器代码的编译器；u编译时实际采用的编译器选项；编译时实际采用的编译器选项；u

19、目标计算机目标计算机。1.2 算法分析初步算法分析初步25对同一语句编译器产生的不同代码1.2 算法分析初步算法分析初步26 数据空间数据空间(data space)：用来存储：用来存储和和值所需的空间。值所需的空间。 一、空间复杂性一、空间复杂性int Abc( int , int , int ) return a+b+b*c+(a+b+c)/(a+b)+4;例例12例例13templateT sum( T a , int n)/计算计算a0:n-1的和的和 T tsum = 0; for ( int i=0; in; i+) tsum+= ai; return tsum;例例14templ

20、ateT Rsum( T a , int n)/计算计算a0:n-1的和的和 if (n0) return Rsum(a,n-1)+an-1; return 0;n数求和数求和递归递归n数求和数求和1.2 算法分析初步算法分析初步271）存储常量和简单变量。）存储常量和简单变量。(1,2,int a, float b等等)2）存储复合变量）存储复合变量 计算方法：结构变量所占空间等于各个成员所计算方法：结构变量所占空间等于各个成员所占空间的累加；数组变量所占空间等于数组大小占空间的累加；数组变量所占空间等于数组大小乘以单个数组元素所占的空间。乘以单个数组元素所占的空间。 例如：例如： doub

21、le a100; 所需空间为所需空间为8100800 int matrixrc; 所需空间为所需空间为 4rc1.2 算法分析初步算法分析初步sizeof (double)sizeof (int)28 环境栈空间环境栈空间(environment stack space)保存函数调用返保存函数调用返回时恢复运行所需要的信息。当一个函数被调用时，下回时恢复运行所需要的信息。当一个函数被调用时，下面数据将被保存在环境栈中：面数据将被保存在环境栈中：返回地址；返回地址；所有局部变量的值、递归函数的传值形式参数的值；所有局部变量的值、递归函数的传值形式参数的值；所有引用参数以及常量引用参数的定义所有引

22、用参数以及常量引用参数的定义。一、空间复杂性一、空间复杂性每当函数每当函数Rsum被调用时，不管该调被调用时，不管该调用是来自外部或第用是来自外部或第4行，行，a的当前赋值、的当前赋值、n的值以及程序运行结束时的返回地的值以及程序运行结束时的返回地址都被存储在环境栈中址都被存储在环境栈中.1.2 算法分析初步算法分析初步templateT Rsum( T a , int n)/计算计算a0:n-1的和的和 if (n0) return Rsum(a,n-1)+an-1; else return 0;29空间复杂度空间复杂度该程序调用深度为该程序调用深度为n11.2 算法分析初步算法分析初步30

23、 在分析空间复杂性中，在分析空间复杂性中，实例特征实例特征的概念非常重要。的概念非常重要。所谓实例特征是指所谓实例特征是指决定问题规模决定问题规模的那些因素。的那些因素。 输入和输出的数量或相关数的大小，如对输入和输出的数量或相关数的大小，如对n 个元个元素进行排序、素进行排序、nn 矩阵的加法等，都可以矩阵的加法等，都可以n 作为作为实例特征，而两个实例特征，而两个mn 矩阵的加法应该以矩阵的加法应该以n 和和m 两个数作为实例特征。两个数作为实例特征。1.2 算法分析初步算法分析初步31令S(P)表示程序P需要的空间，则有S(P) = c + SP(实例特征)c 是一个常量，表示固定部分所

24、需要的空间。主要是一个常量，表示固定部分所需要的空间。主要包括包括指令空间、简单变量以及定长复合变量所占用指令空间、简单变量以及定长复合变量所占用的空间、常量所占用的空间等；的空间、常量所占用的空间等； SP表示可变部分所需要的空间表示可变部分所需要的空间，主要包括复合变量，主要包括复合变量所需的空间（其大小依赖于所解决的具体问题）、所需的空间（其大小依赖于所解决的具体问题）、动态分配的空间（依赖于实例的特征）、递归栈所动态分配的空间（依赖于实例的特征）、递归栈所需的空间（依赖于实例特征）。需的空间（依赖于实例特征）。一、空间复杂性1.2 算法分析初步算法分析初步32利用引用参数利用引用参数t

25、emplate T Abc(T& a, T& b, T& c) return a+b+c+b*c+(a+b+c)/(a+b)+4; 引用参数引用参数 传值参数传值参数例例15T为实例特征：为实例特征：1.a,b,c为引用参数为引用参数: 要保存指向该参数的指针，要保存指向该参数的指针，每个指针每个指针4字节，则字节，则c=12字节，字节，SAbc（实例特征）（实例特征）0。2.若传值参数若传值参数: 则每个参数需要分配大小则每个参数需要分配大小为为sizeof(T)的空间，则的空间，则SAbc(实实例特征例特征) 3*sizeof(T)。1.2 算法分析初步算法分析初步

26、33考察函数考察函数Rsum, 分析其空间复杂度。分析其空间复杂度。 例例161.2 算法分析初步算法分析初步对于对于a: 需要保留一个指针，需要保留一个指针，4字节字节.对于对于n: 需要保留一个需要保留一个int类型的值，类型的值，4字节字节.保留返回地址，保留返回地址，4字节字节.每一次调用每一次调用Rsum需要需要12个字节的栈空间。个字节的栈空间。由于递归的深度为由于递归的深度为n1，所以需要，所以需要12(n+1)字节的字节的递归栈空间，因而递归栈空间，因而SRsum(n)=12(n+1)。templateT Rsum( T a , int n)/计算计算a0:n-1的和的和 if

27、 (n0) return Rsum(a,n-1)+an-1; return 0;34Theoretical analysis of time efficiencyTime efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input sizelBasic operation: the operation that contributes most towards the running time of the algorithm. T(n

28、) copC(n)running timeexecution timefor basic operationNumber of times basic operation is executedinput size35二、时间复杂性 time efficiencyl一个程序一个程序P所占用的时间所占用的时间T (P)=编译时间编译时间+运行时间运行时间l估算运行时间的方法：估算运行时间的方法： 1）操作计数：找出一个或多个）操作计数：找出一个或多个关键关键操作，确定这些关操作，确定这些关键操作所需要的执行时间；键操作所需要的执行时间； 2）执行步数：确定程序总的执行步数。）执行步数：确定程序总

29、的执行步数。l实验方法：利用编译器提供的时间函数来计算。实验方法：利用编译器提供的时间函数来计算。 1.2 算法分析初步算法分析初步36估算运行时间的方法估算运行时间的方法选择一种或多种（如加、乘和比较等），然后确定选择一种或多种（如加、乘和比较等），然后确定这种（些）操作分别执行了多少次。这种（些）操作分别执行了多少次。令令n代表程序的实例特征代表程序的实例特征，那么，那么， TP的计算公式为：的计算公式为：TP（n）= c1ADD(n) + c2SUB(n) + c3MUL(n) + c4DIV(n)+1.2 算法分析初步算法分析初步c1、c2、c3、c4分别表示，一次分别表示，一次加、减

30、、乘、加、减、乘、 除操作所需的时除操作所需的时间。函数间。函数ADD (n) 、SUB (n) 、MUL (n) 、DIV (n)分别表示程分别表示程序序P中，所使用的加、减、乘、中，所使用的加、减、乘、除操作的次数。除操作的次数。这种方法是否成功取决这种方法是否成功取决于识别关键操作的能力，于识别关键操作的能力，这些关键操作对时间复这些关键操作对时间复杂性的影响最大。杂性的影响最大。37templateint Max(T a , int n) / 寻找寻找a 0 : n - 1 中的最大元素中的最大元素 int pos = 0; for (int i = 1; i n; i+) if (a

31、pos ai) pos = i; return pos;例例17返回数组返回数组a0:n-1中最大元素的位置中最大元素的位置关键操作？关键操作？关键操作：关键操作：比较操作比较操作For循环中每次需循环中每次需要执行一次比较，所以总要执行一次比较，所以总的比较次数为的比较次数为n-1。1.2 算法分析初步算法分析初步38templatevoid Rank(T a , int n, int r )/ 计算计算a0:n-1中中n个元素的排名个元素的排名 for( int i =0;in; i+) ri = 0;/初始化初始化 /逐对比较所有的元素逐对比较所有的元素 for(i = 0; in; i

32、+) for(int j = 0; ji; j+) if (aj = ai) ri+; else rj+;1.2 算法分析初步算法分析初步例例18元素在队列中的名次（元素在队列中的名次（rank）可定义为队列中所有）可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的比它小的元素数目加上在它左边出现的与它相同的元素数目。例如元素数目。例如a=4,3,9,3,7作为队列，则各元素的作为队列，则各元素的名次名次r=2, 0, 4, 1, 3关键操作：比较操作关键操作：比较操作对于对于i 的每个取值，比的每个取值，比较的次数为较的次数为i 总的比较次数为：总的比较次数为：1 + 2 + 3

33、 +n-1 = (n-1)n / 239templatevoid Insert(T a, int& n, const T& x) / 向有序数组向有序数组a 0 : n-1 中插入元素中插入元素x / 假定假定a 的大小超过的大小超过n int i; for (i = n-1; i = 0 & x 时有时有(T(N)- )/T(N)0)，称，称 是是T(N)当当N 时的渐进性态时的渐进性态)(NT)(NT)(NT比如比如T(N)=3N2+4NlogN+7时，时， 的一个答案是的一个答案是3N2，因为这时，因为这时)(NT07log437log4)(/)()(2NNNNN

34、NTNTNT1.2 算法分析初步算法分析初步44 分析算法的复杂性的目的在于比较求解同一问题的分析算法的复杂性的目的在于比较求解同一问题的两个不同算法的效率，而当要比较的两个算法的渐进复两个不同算法的效率，而当要比较的两个算法的渐进复杂性的阶不相同时，只要能确定出各自的阶就可以判定杂性的阶不相同时，只要能确定出各自的阶就可以判定哪一个算法的效率高。也就是渐进复杂性只要关心哪一个算法的效率高。也就是渐进复杂性只要关心 的阶就够了，不必关心包含在其中的常数因子。的阶就够了，不必关心包含在其中的常数因子。 即只要考察当问题的规模充分大时，算法复杂性在即只要考察当问题的规模充分大时，算法复杂性在渐进意

35、义下的阶。渐进意义下的阶。)(NT1.2 算法分析初步算法分析初步一个算法的复杂度是一个算法的复杂度是 3n2+5n+93n2另一个为另一个为2n3+7n2n345渐进意义下的记号：渐进意义下的记号：O, ,lf(N)和和g(N)是定义在正整数上的正函数。是定义在正整数上的正函数。定义定义1.1 1.1 如果存在两个正常数如果存在两个正常数c和和N0,对于所有的对于所有的NN0，有，有f(N) Cg(N)，则记作：，则记作：f(N)= O(g(N)。N0f(N)g(N)1.2 算法分析初步算法分析初步当说一个算法具有当说一个算法具有O(g(n)的计算时间时，指的的计算时间时，指的就是如果此算法

36、用就是如果此算法用n值不变的同一类数据在某台值不变的同一类数据在某台机器上运行时，所用的时间总是小于机器上运行时，所用的时间总是小于g(n)的一个的一个常数倍。常数倍。g(n)是计算时间是计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数的数量级就是量级就是g(n)46Example因为对所有的因为对所有的N N11有有3 3N N44N N，我们有，我们有3 3N N= =O O( (N N););因为当因为当N N11时有时有N N+10241025+10241025N N，我们有，我们有N N+1024=+1024=O O( (N N););因为当因为当N N1010时有时有2

37、 2N N 2 2+11+11N N-103-103N N 2 2, ,我们有我们有 2 2N N 2 2+11+11N N-10=-10=O O( (N N 2 2););因为对所有因为对所有N N11有有N N 2 2N N 3 3 , ,我们有我们有N N 2 2= =O O( (N N 3 3););1.2 算法分析初步算法分析初步47Example作为一个反例作为一个反例N 3O(N 2)因为若不然，则存在正的常数因为若不然，则存在正的常数C和自然数和自然数N0 ,使得当使得当NN0有有N 3CN 2,即即NC。显。显然，当取然，当取N=maxN0,C+1时这个不等式时这个不等式不成

38、立，所以不成立，所以N 3O(N 2)。1.2 算法分析初步算法分析初步48l定理定理1.1： 若若A(n)=amnm+a1n+a0是一个是一个m次多项式，次多项式，则则A(n)=O(nm)。l定理表明，变量定理表明，变量n的固定阶数为的固定阶数为m的任一多项式，的任一多项式，与此多项式的最高阶与此多项式的最高阶nm同阶。因此，一个计算时间为同阶。因此，一个计算时间为m阶多项式的算法，其时间都可以用阶多项式的算法，其时间都可以用O(nm)来表示。来表示。例如，一个算法的数量级为例如，一个算法的数量级为c1nm1,c2nm2,cknmk的的k个语个语句，则算法的数量级计算时间就是句，则算法的数量

39、级计算时间就是c1nm1+c2nm2+cknmk=O(nm) 其中其中m=maxmi|1ik。1.2 算法分析初步算法分析初步49符号符号O运算性质：运算性质：（1）O(f)+O(g)=O(max(f,g)（2）O(f)+O(g)=O(f+g)（3）O(f)O(g)=O(fg)（4）如果）如果g(N)=O(f(N)，则，则O(f)+O(g)=O(f)（5）O(Cf(N)=O(f(N)，其中，其中C是一个正的常数是一个正的常数（6）f=O(f)1.2 算法分析初步算法分析初步50性质（1）证明 设设F(N)=O(f)。根据符号。根据符号O的定义，存在正常数的定义，存在正常数C1和自然数和自然数N

40、1，使，使得对所有的得对所有的N N1，有，有F(N) C1 f(N)。 类似地，设类似地，设G(N)=O(g)，则存在正的常数，则存在正的常数C2和自然数和自然数N2，使得对，使得对所有的所有的N N2 , 有有G(N) C2g(N)。 令令C3=maxC1,C2，N3=maxN1,N2，h(N)=maxf,g。则对所有的。则对所有的N N3，有，有 F(N) C1 f(N) C1h(N) C3h(N) 类似的，有类似的，有 G(N) C2g(N) C2h(N) C3h(N) 因而因而 O(f)+O(g)=F(N)+G(N) C3h(N)+ C3h(N) =2 C3h(N) =O(h) =O

41、(max(f,g)1.2 算法分析初步算法分析初步51l根据符号根据符号O的定义，用它评估算法的复杂的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上性，得到的只是当规模充分大时的一个上界，这个上界的阶越低则评估就越精确，界，这个上界的阶越低则评估就越精确，结果就越有价值。结果就越有价值。1.2 算法分析初步算法分析初步52符号的定义l定义定义1.2 ：如果存在两个正常数：如果存在两个正常数C和自然数和自然数N0，使，使得当得当N N0时，有时，有f(N)Cg(N)，则称函数，则称函数f(N)当当N充分大时下有界；且充分大时下有界；且g(N)是它的一个下界，记为是它的一个下界，记为

42、f(N)=(g(N)。 这时我们说这时我们说f(N)的阶不低于的阶不低于g(N)的阶。的阶。1.2 算法分析初步算法分析初步53对于所有对于所有n，有，有f(n)=3n+2 3n，因此，因此f(n) = (n)。同样地，同样地，f(n)= 3n+3 3n，所以有，所以有f(n) = (n)。f(n) = 100n+6 100n，所以，所以100n+6 = (n)。因而因而3n+2，3n+3和和100n+6都是带有下限的线性函数。都是带有下限的线性函数。1.2 算法分析初步算法分析初步54对于所有的对于所有的n0，有，有f(n) = 10n2+4n+2 10n2，因此，因此f(n)= (n2)。

43、同样地，同样地，1000n2 + 100n-6 = (n2)。由于由于6*2n+n2 6*2n ，所以，所以6*2n+n2 = (2n)。1.2 算法分析初步算法分析初步55也可以得到也可以得到:3n+3 = ( 1 )，10n2 + 4n + 2 = (n)，10n2 + 4n + 2 = ( 1 )，6 * 2n + n2 = (n100 ) ,6 * 2n + n2 = (n50.2 ), 6 * 2n + n2 = (n2 ), 6 * 2n + n2 = (n)，6 * 2n + n2 = ( 1 )。1.2 算法分析初步算法分析初步56l定理定理1.2：如果：如果f(n) =am

44、nm+.+a1n+a0 且且am 0，则，则f(n) = (nm )。l这个定义的优点是与这个定义的优点是与O的定义对称，缺点是的定义对称，缺点是f(N)对自然对自然数的不同无穷子集有不同的表达式，且有不同的阶时，数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画出不能很好地刻画出f(N)的下界。比如当的下界。比如当 100 N为正偶数为正偶数 f(N)= 6N2 N为正奇数为正奇数l按照定义，得到按照定义，得到f(N)=(1),这是个平凡的下界，对算法这是个平凡的下界，对算法分析没有什么价值。分析没有什么价值。1.2 算法分析初步算法分析初步57 ，o 的定义的定义l 定义定义 f(N)= (g(N)，当且仅当，当且仅当f(N)=O(g(N)且且f(N)=(g(N)。这时，我们说。这时，我们说f(N)与与g(N)同阶。同阶。lo 如果对于任意给定的如果对于任意给定的0，都存在正整数，都存在正整数N0，使，使得当得当N N0时有时有f(N)/g(N)，则称函数，则称函数f(N)当当N充分大时的阶比充分大时的阶比g(N)低，记为低，记为f(N)=o(g(N)。l例如：例如：4NlogN+7=o(3N2+4NlogN+7)1.2 算法分析初步算法分析初步581.2 算法分析初步算法分析初