专题2算法描述及分析

1、1算法设计与分析算法设计与分析Design and Analysis to Algorithms2算法算法 = 控制结构控制结构 + 原操作原操作表示算法的语言主要有：表示算法的语言主要有：n自然语言自然语言n流程图流程图n盒图盒图nPAD图图n伪代码伪代码n计算机程序设计语言计算机程序设计语言1.2 算法描述算法描述 31 1自然语言自然语言自然语言是人们日常所用的语言。使用这些语言，不用专自然语言是人们日常所用的语言。使用这些语言，不用专门训练，所描述的算法也通俗易懂。门训练，所描述的算法也通俗易懂。自然语言描述算法的缺点：自然语言描述算法的缺点： 自然语言的歧义性易导致算法执行的不确定性

2、。自然语言的歧义性易导致算法执行的不确定性。 自然语言语句一般太长导致描述的算法太长。自然语言语句一般太长导致描述的算法太长。 当算法中循环和分支较多时就很难清晰表示。当算法中循环和分支较多时就很难清晰表示。 不便翻译成程序设计语言理解的语言。不便翻译成程序设计语言理解的语言。4 2 2流程图流程图 n流程图是描述算法的常用流程图是描述算法的常用工具，它采用美国国家标工具，它采用美国国家标准化协会准化协会(ANSI)(ANSI)规定的一规定的一组图形符号来表示算法流组图形符号来表示算法流程图，可以很方便的表示程图，可以很方便的表示顺序和循环结构。顺序和循环结构。算法的入口和出口算法的入口和出口

3、加工、处理加工、处理条件条件控制流控制流连接点连接点5A顺序结构顺序结构expBABTF双分支选择结构双分支选择结构DoCase1Case2Case n多分支选择结构多分支选择结构expFAT当型循环结构当型循环结构expTF直到型循环结构直到型循环结构A6 2 2流程图流程图 主要缺点：主要缺点： 使算法设计人员过早考虑算法使算法设计人员过早考虑算法控制流程，而不去考虑全局结控制流程，而不去考虑全局结构，不利于逐步求精。构，不利于逐步求精。 随意性太强，结构化不明显。随意性太强，结构化不明显。 不易表示数据结构。不易表示数据结构。 层次感不明显。层次感不明显。NYr等于等于0?输出输出n的值

4、的值输入正整数输入正整数m和和n开始开始结束结束m n; n rrm被被n除的余数除的余数rm被被n除的余数除的余数73 3盒图（盒图（NSNS流程图）流程图）盒图(也称NS图)是由Nassi和Shneiderman提出的一种符号结构化程序设计原则的图形描述工具。盒图有以下特点：功能域(即一个特定控制结构的作用域)明确；无法任意转移控制；容易确定全局数据和局部数据的作用域；容易表示嵌套关系，也可以表示模块的层次结构。83 3盒图（盒图（NSNS流程图）流程图）93 3盒图（盒图（NSNS流程图）流程图） （1 1）盒图具有以下优点：）盒图具有以下优点： 层次感强、嵌套明确。层次感强、嵌套明确。

5、 支持自顶向下、逐步求精。支持自顶向下、逐步求精。 容易转换成高级语言源算法。容易转换成高级语言源算法。（2 2）主要缺点：）主要缺点： 不易扩充和修改，不易描述大型复杂算法。不易扩充和修改，不易描述大型复杂算法。输入正整数输入正整数m和和n rm被被n除的余数除的余数 m n; n rrm被被n除的余数除的余数 当当r不等于不等于 0输出输出n的值的值 104 4 PADPAD图图11 PAD PAD图的主要优点：图的主要优点： 设计出来的算法必是结构化的。设计出来的算法必是结构化的。PADPAD图描绘的算法结构清晰。图描绘的算法结构清晰。用用PADPAD图表现的算法逻辑，易读、易懂、易记。

6、图表现的算法逻辑，易读、易懂、易记。容易用软件工具自动将容易用软件工具自动将PADPAD图转换成高级语言源算法。图转换成高级语言源算法。既可用于表示算法逻辑，也可用于描绘数据结构。既可用于表示算法逻辑，也可用于描绘数据结构。支持自顶向下、逐步求精。支持自顶向下、逐步求精。缺点：缺点：由于是图形符号书写、编辑、录入不方便。由于是图形符号书写、编辑、录入不方便。4 4 PADPAD图图 问题分析图问题分析图(Problem Analysis Diagram, (Problem Analysis Diagram, 简称简称PAD)PAD)表示表示的算法是一个二维树形结构图，层次感强、嵌套明确且有的算

7、法是一个二维树形结构图，层次感强、嵌套明确且有明确的控制流程。明确的控制流程。12例：例：问题分析图实例问题分析图实例135 5伪代码伪代码 伪代码是用介于自然语言和计算机语言之间的伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因文字和符号来描述算法的工具。它不用图形符号，因此书写方便，格式紧凑，易于理解，便于用计算机程此书写方便，格式紧凑，易于理解，便于用计算机程序设计语言实现。序设计语言实现。 如：如：类类SPARKS/SPARKS/类类C/C/类类C C146程序设计语言的缺点：程序设计语言的缺点： 算法的基本逻辑流程难于遵循。与自然语言一样，算法的

8、基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的，当算法的逻辑流程较程序设计语言也是基于串行的，当算法的逻辑流程较为复杂时这个问题就变得更加严重。为复杂时这个问题就变得更加严重。 特定程序设计语言编写的算法限制了与他人的交流，特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决。不利于问题的解决。 要花费大量的时间去熟悉和掌握某种特定的程序设要花费大量的时间去熟悉和掌握某种特定的程序设计语言。计语言。 要求描述计算步骤的细节而忽视算法的本质。要求描述计算步骤的细节而忽视算法的本质。 需要考虑语法细节，而扰乱算法设计的思路。需要考虑语法细节，而扰乱算法设计的思路。 考虑

9、到程序设计语言不断更新，不适于描述算法。考虑到程序设计语言不断更新，不适于描述算法。 算法设计一般不用程序设计语言直接描述。算法设计一般不用程序设计语言直接描述。151. 算法分析的目的算法分析的目的 通过对算法分析，在把算法变成程序实际运行前，通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。行好算法，改进差算法，避免无益的人力和物力浪费。 1.3 算法分析算法分析162. 重要的假设和约定重要的假设和约定1）计算机模型的假设）计算机模型的假设n 计算机形式理

10、论模型计算机形式理论模型 ：Turing机模型机模型n 通用计算机模型：通用计算机模型： 单处理器：每次执行程序中一条指令单处理器：每次执行程序中一条指令 有足够的有足够的“内存内存” 能在固定的时间内存取数据单元能在固定的时间内存取数据单元172）计算的约定）计算的约定n确定使用什么样的运算及其执行时间。确定使用什么样的运算及其执行时间。n从计算时间上，运算的分类：从计算时间上，运算的分类： 时间囿界于常数的运算时间囿界于常数的运算：每种运算的执行时间：每种运算的执行时间不同，但一般只花不同，但一般只花 一个一个固定量固定量时间（单位时间）时间（单位时间）就可完成。就可完成。 基本算术运算基

11、本算术运算 字符运算字符运算 赋值赋值运算运算 过程调用等过程调用等182）计算的约定）计算的约定 其他运算其他运算：特点：运算时间：特点：运算时间无定量无定量 字符串操作：与字符串中字符的数量成正比。字符串操作：与字符串中字符的数量成正比。 记录操作：与记录的属性数、属性类型等有关。记录操作：与记录的属性数、属性类型等有关。 如何分析非时间囿界于常数的运算？如何分析非时间囿界于常数的运算？ 如：如：Tstring = Length（String）* tcharn算法的执行时间算法的执行时间=Fi*tiqFi是算法中用到的某种运算是算法中用到的某种运算i的次数，的次数， ti是该运算执行是该运

12、算执行一次所用时间。一次所用时间。191.有些计算机需要用户提供程序运行时有些计算机需要用户提供程序运行时 间的上限，一旦达到这个上限，程序间的上限，一旦达到这个上限，程序 将被强制结束。将被强制结束。2.正在开发的程序可能需要提供一个满正在开发的程序可能需要提供一个满 意的实时响应。意的实时响应。时间复杂性和空间复杂性时间复杂性和空间复杂性3.算法复杂性算法复杂性为什么要考虑时间复杂性？为什么要考虑时间复杂性？201.1.多用户系统中运行时，需指明分配多用户系统中运行时，需指明分配给该程序的内存大小。给该程序的内存大小。2.2.可提前知道是否有足够可用的内存可提前知道是否有足够可用的内存来运

13、行该程序。来运行该程序。3.3.一个问题可能有若干个内存需求各一个问题可能有若干个内存需求各不相同的解决方案，从中择取。不相同的解决方案，从中择取。4.4.利用空间复杂性来估算一个程序所利用空间复杂性来估算一个程序所能解决问题的最大规模。能解决问题的最大规模。考虑程序的空间复杂性的理由：考虑程序的空间复杂性的理由：214. 如何进行算法分析？如何进行算法分析？n事前分析事前分析：就算法本身，通过对其执行性能的理论分析，：就算法本身，通过对其执行性能的理论分析， 得出关于算法特性得出关于算法特性时间和空间时间和空间的一个特征的一个特征 函数（函数（、）与计算机软硬件没有直接与计算机软硬件没有直接

14、 关系。关系。n事后测试事后测试：将算法编制成程序后放到计算机上运行，收集：将算法编制成程序后放到计算机上运行，收集 其执行时间和空间占用等统计资料，进行分析其执行时间和空间占用等统计资料，进行分析 判断判断直接与物理实现有关。直接与物理实现有关。221）事前分析）事前分析n目的：试图得出关于算法执行特性的一种形式描目的：试图得出关于算法执行特性的一种形式描 述，以述，以“理论上理论上”衡量算法衡量算法 “好坏好坏”。n如何给出反映算法执行特性的描述如何给出反映算法执行特性的描述？ 最直接方法：最直接方法：统计算法中各种运算的执行情况：统计算法中各种运算的执行情况： 运用了哪些运算运用了哪些运

15、算 每种运算被执行的次数每种运算被执行的次数 该种运算执行一次所花费的时间该种运算执行一次所花费的时间 算法的执行时间算法的执行时间=Fi*ti23估算执行时间的方法估算执行时间的方法 选择一种或多种（如加、乘和比较等），然后确定选择一种或多种（如加、乘和比较等），然后确定这种（些）操作分别执行了多少次。这种（些）操作分别执行了多少次。令令n代表程序实例特征，则执行时间计算公式为：代表程序实例特征，则执行时间计算公式为：TP（n）= c1ADD(n) + c2SUB(n) + c3MUL(n) + c4DIV(n)+c1、c2、c3、c4分别表示一次加、分别表示一次加、减、乘、减、乘、 除操作

16、所需的时间。除操作所需的时间。函数函数ADD (n) 、SUB (n) 、MUL (n) 、DIV (n)分别表示程分别表示程序序P中，所使用的加、减、乘、中，所使用的加、减、乘、除操作的次数。除操作的次数。这种方法是否成功取决这种方法是否成功取决于识别关键操作的能力，于识别关键操作的能力，这些关键操作对时间复这些关键操作对时间复杂性的影响最大。杂性的影响最大。一条语句在整个程序运行时实际执行时间一条语句在整个程序运行时实际执行时间= 频率计数频率计数 * 每执行一次该语句所需的时间每执行一次该语句所需的时间24n频率计数：频率计数：算法中算法中语句语句或或运算运算的执行次数。的执行次数。 例

17、：例： x=x+y for (i =1;i=n;i+) for (i =1;i=n;i+) x=x+y; for (j =1;j=n;j+) x=x+y; (a) (b) (c) 分析：分析： (a)： x=x+y执行了执行了1次次 (b)： x=x+y执行了执行了n次次 (c)： x=x+y执行了执行了n2次次 注：在事前分析中，只限于确定与所使用机器及其他环境注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。因素无关的频率计数，依此建立一种理论上分析模型。25n数量级数量级语句的数量级语句的数量级：语句的执行频率。：语句的执行频率。例：例：1

18、，n ，n2 算法的数量级算法的数量级：算法包含所有语句的执行频率之和。：算法包含所有语句的执行频率之和。 算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。 例：求解同一问题的三个算法分别具有例：求解同一问题的三个算法分别具有n, n2 , n3数量级。数量级。 若若n=10，则可能的执行时间将分别是，则可能的执行时间将分别是10，100，1000 个个单位时间单位时间与环境因素无关。与环境因素无关。26n 计算时间计算时间/频率计数的表示函数频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）通过事前分析给出算法计算时间（频率计数）的一个的

19、一个函数函数表示形式，一般记为与表示形式，一般记为与输入规模输入规模n有关有关的函数形式：的函数形式：f(n)注：最高次项与函数整体的关系注：最高次项与函数整体的关系n空间特性分析（与时间特性的分析类似，略）空间特性分析（与时间特性的分析类似，略） 272）事后测试）事后测试n目的：目的：运行程序，确定程序实际耗费的时间运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论与空间，验证先前的分析结论包括正确包括正确性、执行性能等，比较、优化所设计的算法。性、执行性能等，比较、优化所设计的算法。n分析手段：分析手段：作时、空性能分布图。作时、空性能分布图。285. 计算时间的渐近表示计算时间

20、的渐近表示记：算法的计算时间为记：算法的计算时间为f(n) 数量级限界函数为数量级限界函数为g(n)其中，其中，n n是输入或输出规模的某种测度。是输入或输出规模的某种测度。n f(n)表示算法的表示算法的“实际实际”执行时间。执行时间。n g(n)是是形式简单形式简单的函数，如的函数，如nm，logn，2n，n!等。是事等。是事前分析中通过对计算时间或频率计数统计分析所得的前分析中通过对计算时间或频率计数统计分析所得的与机与机器及语言无关器及语言无关的函数。的函数。 以下给出算法执行时间：以下给出算法执行时间：上界上界（）、）、下界下界（）、）、“平均平均”（ ）的定义。）的定义。29渐进意

21、义下的记号：渐进意义下的记号：O, , ,定义定义1.1 如果存在两个正常数如果存在两个正常数c和和N0,对于所有的对于所有的NN0，有，有| |f(N)| |C| |g(N)| |，则记作：，则记作：f(N)= O(g(N)。N0f(N)g(N)当说一个算法具有当说一个算法具有O(g(n)的计算时间时，指的的计算时间时，指的就是如果此算法用就是如果此算法用n值不变的同一类数据在某台值不变的同一类数据在某台机器上运行时，所用的时间总是小于机器上运行时，所用的时间总是小于g(n)的一个的一个常数倍。常数倍。g(n)是计算时间是计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数的数量级就

22、是量级就是g(n)。30Example因为对所有的因为对所有的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 2N N2 2+11+11N N-103-103N N2 2, ,所以有所以有 2 2N N2 2+11+11N N-10=-10=O O( (N N2 2) )因为对所有因为对所有N N11有有N N2 2N N3 3, ,我们有我们有N N2 2=

23、=O O( (N N3 3) )作为一个反例作为一个反例N N3 3O O( (N N2 2),),因为若不然，则存在正因为若不然，则存在正的常数的常数C C和自然数和自然数N N0 0, ,使得当使得当N NN N0 0，有有N N3 3CNCN2 2, ,即即N NC C。显然，当取。显然，当取N N=max=maxN N0 0, ,C C+1+1时这个不等式时这个不等式不成立，所以不成立，所以N N3 3O O( (N N2 2) )31n多项式定理多项式定理:定理定理1.1 若若A(n) = amnm+a+a1 1n+an+a0 0是一个是一个m m次多项次多项 式，则有式，则有A(n

24、)=A(n)=( (nm) ) 即：变量即：变量n n的固定阶数为的固定阶数为m m的任一多项式，与此多的任一多项式，与此多 项式的最高阶项式的最高阶nm同阶。同阶。 证明：取证明：取n n0 0=1,=1,当当nnnn0 0时，有时，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令令c= |am|+|am-1|+|a0| 定理得证。定理得证。32n 计算时间的数量级对算法有效性的影响计算时间的数量级对算法有效性的影响 数量级数量级的大小对算法的有效性有的大小对算法的有效性有决定性决定性的影响

25、。的影响。 例：假设解决同一个问题的两个算法，它们都有例：假设解决同一个问题的两个算法，它们都有n个输个输入，计算时间的数量级分别是入，计算时间的数量级分别是n2和和nlogn。则：。则： n=1024：分别需要：分别需要1048576和和10240次运算。次运算。 n=2048：分别需要：分别需要4194304和和22528次运算。次运算。分析：在分析：在n加倍的情况下，一个加倍的情况下，一个(n(n2 2) )的算法计算时间增长的算法计算时间增长4 4 倍，而一个倍，而一个(nlogn)(nlogn)算法则只用算法则只用两两倍多一点的时间即倍多一点的时间即 可完成。可完成。33 算法分类（

26、计算时间）算法分类（计算时间）多项式时间算法：多项式时间算法：可用多项式（函数）对其计算可用多项式（函数）对其计算时间限界的算法。时间限界的算法。 常见的多项式限界函数有：常见的多项式限界函数有： (1) (1) (logn) (logn) (n) (n) (nlogn) (nlogn) (n(n2 2) ) (n(n3 3) )指数时间算法：指数时间算法：计算时间用指数函数限界的算法计算时间用指数函数限界的算法 常见的指数时间限界函数：常见的指数时间限界函数： (2(2n n) ) (n(n！) ) 0 0，则则f(n)=f(n)=(n(nm m ) )。n该定义的优点是与该定义的优点是与O

27、 O的定义对称，缺点是的定义对称，缺点是f f( (N N) )对自然对自然数的不同无穷子集有不同的表达式，且有不同的阶数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画出时，不能很好地刻画出f f( (N N) )的下界。的下界。比如当比如当 100 N为正偶数为正偶数 f(N)= 6N2 N为正奇数为正奇数n按照定义，得到按照定义，得到f f( (N N)=)=(1),(1),这是个平凡的下界，对这是个平凡的下界，对算法分析没有什么价值。算法分析没有什么价值。38定义定义1.3 如果存在正常数如果存在正常数c1，c2和和n0，对于所有的，对于所有的nn0，有，有c1|g(N)|

28、 |f(N)| c2|g(N)| 则记作则记作 f(N)= (g,(N)含义：含义：n算法在最好和最坏情况下的计算时间就一个常数因子范算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：围内而言是相同的。可看作： 既有既有f(N)=f(N)=(g(N)(g(N)，又有，又有f(N)=f(N)=(g(N)(g(N)“平均情况平均情况”限界函数限界函数3940 一个具体算法的时间复杂度和空间复杂度往往不独一个具体算法的时间复杂度和空间复杂度往往不独立，在算法设计中要在时间效率和空间效率之间折衷。立，在算法设计中要在时间效率和空间效率之间折衷。n非递归算法分析非递归算法分析 a

29、仅依赖于问题规模的时间复杂度仅依赖于问题规模的时间复杂度 有一类简单的问题，其操作具有普遍性，也就是说对所有一类简单的问题，其操作具有普遍性，也就是说对所有的数据均等价地进行处理。有的数据均等价地进行处理。6. 算法分析实例算法分析实例41【例例1.7】交换交换i i和和j j的内容的内容。 Temp=i； i=j； j=temp； 以上三条单个语句的频度均为以上三条单个语句的频度均为1 1，该算法段的执行时，该算法段的执行时间是一个与问题规模间是一个与问题规模n n无关的常数。算法的时间复杂度为无关的常数。算法的时间复杂度为常数阶，记作常数阶，记作T(n)=(1)T(n)=(1)。 如果算法

30、的执行时间不随着问题规模如果算法的执行时间不随着问题规模n n的增加而增长，的增加而增长，即使算法中有上千条语句即使算法中有上千条语句, ,其执行时间也不过是一个较大其执行时间也不过是一个较大的常数。此类算法的时间复杂度是的常数。此类算法的时间复杂度是(1)(1)。 42【例例1.8】循环次数直接依赖规模循环次数直接依赖规模n变量计数之一变量计数之一。 (1) x=0;y=0; (2) for(k=1;k=n;k+) (3) x+; (4) for(i=1;i=n;i+) (5) for(j=1;j=n;j+) (6) y+; 该算法段的时间复杂度为该算法段的时间复杂度为T(n)=(nT(n)

31、=(n2 2) )。 当有若干个循环语句时，算法的时间复杂度是由嵌套层数当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度最多的循环语句中最内层语句的频度f(n)f(n)决定的。决定的。43【例例1.91.9】循环次数间接依赖规模循环次数间接依赖规模n-n-变量计数之二。变量计数之二。 (1) x=1； (2) for(i=1；i=n；i+) (3) for(j=1；j=i；j+) (4) for(k=1；k=0 and Aik ) (3) i=i-1； (4) return i； 此算法的频度不仅与问题规模此算法的频度不仅与问题规模n有关，还与输入实例中有关，

32、还与输入实例中A的各元素的各元素取值及取值及k的取值有关：的取值有关： 1. 若若A中没有与中没有与k相等的元素，则相等的元素，则(2)频度频度f(n)=n(最坏情况最坏情况)； 2. 若若A最后一个元素等于最后一个元素等于k ，则，则(2)频度频度f(n)是常数是常数1(最好情况最好情况);45 在求在求平均情况平均情况时，一般地假设查找不同元素的概率时，一般地假设查找不同元素的概率P P是是相同相同的的, ,则算法的平均复杂度为：则算法的平均复杂度为： 若对于查找不同元素的概率若对于查找不同元素的概率P P不相同不相同时，其算法复杂度时，其算法复杂度就只能做近似分析，或在构造更好的算法或存

33、储结构后，就只能做近似分析，或在构造更好的算法或存储结构后，做较准确的分析。做较准确的分析。46【例例1.111.11】求求N N！ 构造算法中的两个步骤：构造算法中的两个步骤： 1 1）N!=NN!=N* *(N-1)(N-1)！(n1) 2(n1) 2）0!=10!=1， 1!=1(n=0,1)1!=1(n=0,1)。 递归算法如下：递归算法如下： 以以n=3n=3为例，调用过程如下：为例，调用过程如下： fact(3)-fact(2)-fact(1)-fact(2)-fact(3)fact(3)-fact(2)-fact(1)-fact(2)-fact(3) 递递 归归 回回 溯溯 n递

34、归算法分析递归算法分析47【例例1.11】求求N！ 递归方程为：递归方程为： T(n)=T(n-1)+O(1) 其中其中O(1)为一次乘法操作。为一次乘法操作。 迭代求解过程如下：迭代求解过程如下： T(n)=T(n-2)+O(1)+O(1) =T(n-3)+O(1)+O(1)+O(1) =O(1)+O(1)+O(1)+O(1) =n*O(1) =O(n)48【例例1.12】抽象地考虑以下递归方程，且假设抽象地考虑以下递归方程，且假设n=2n=2k k，则则迭代求解过程如下：迭代求解过程如下： T(n) =O(n) 49【例例1.13】一个楼有一个楼有n n个台阶，有一个人上楼有时一次个台阶，

35、有一个人上楼有时一次跨一个台阶，有时一次跨两个台阶，编写一个算法，计算跨一个台阶，有时一次跨两个台阶，编写一个算法，计算此人有几种不同的上楼方法，并分析算法的时间复杂度。此人有几种不同的上楼方法，并分析算法的时间复杂度。 解：设计一个递归算法。解：设计一个递归算法。 H(int n) if (n2时间复杂度时间复杂度(设设T(n)分析：分析：50【例例1.14】抽象地考虑以下递归方程，且假设抽象地考虑以下递归方程，且假设n=2n=2k k，则则迭迭 代求解过程如下：代求解过程如下： T(n)=2T(n/2)+O(n) =4T(n/4)+2O(n/2)+O(n) = =O(n)+O(n)+ +O

36、(n)+O(n)+O(n) =kO(n) =O(kn) =O(nlog2 n) 51【例例1.15】抽象地考虑以下递归方程，迭代求解过程如下：抽象地考虑以下递归方程，迭代求解过程如下： T(n)=T(n/3)+T(2n/3)+n =T(n/9)+T(2n/9)+n/3+T(2n/9)+T(4n/9)+2n/3 = n=(k+1)n=n(log n+1)i=0k2/3nn/3n/92n/92n/34n/92n/9设最长路径长度为设最长路径长度为k，(2/3) n=1k=log nk2/3 T(n) =O(nlog n)2/352n提高算法质量提高算法质量 首先要提醒大家，不要一味地追求算法的效率

37、，应当首先要提醒大家，不要一味地追求算法的效率，应当在满足正确性、可靠性、健壮性、可读性等质量因素的前在满足正确性、可靠性、健壮性、可读性等质量因素的前提下，设法提高算法的效率。提下，设法提高算法的效率。 看两组操作：看两组操作： (1) a=a+b； b=a-b；a=a-b； (2) t=a； a=b； b=t； 两组操作的功能都是：两组操作的功能都是：“交换变量交换变量a a、b b中的数据中的数据”。虽然第一组操作节省了一个存储空间，但失去了可读性，虽然第一组操作节省了一个存储空间，但失去了可读性，是不可取的。是不可取的。53 下面给出一些原则上的建议：下面给出一些原则上的建议：a.a.

38、保证正确性、可靠性、健壮性、可读性保证正确性、可靠性、健壮性、可读性 1 1）当心视觉上不易分辨的操作符发生书写错误。）当心视觉上不易分辨的操作符发生书写错误。 2 2）算法中的变量）算法中的变量( (指针、数组指针、数组) )在被引用前，一定要在被引用前，一定要有确切有确切 的的含义，或是被赋值或是经模块接口含义，或是被赋值或是经模块接口传递信息。传递信息。 3 3）算法中要当心变量发生上溢或下溢）算法中要当心变量发生上溢或下溢( (数组的下标越界数组的下标越界) )。 4 4）写算法时就要考虑可能出现错误的情况，提示执行错）写算法时就要考虑可能出现错误的情况，提示执行错 误处理算法。误处理

39、算法。 5 5）编写算法时区别问题的循环条件和停止条件，不要误用。）编写算法时区别问题的循环条件和停止条件，不要误用。 6 6）注意算法中循环体或条件体的位置，不要误把循环体）注意算法中循环体或条件体的位置，不要误把循环体 内的操作写在循环体外或者出现相反错误。内的操作写在循环体外或者出现相反错误。54b b提高效率提高效率1 1）以提高算法的全局效率为主，提高局部效率为辅。）以提高算法的全局效率为主，提高局部效率为辅。 2 2）在优化算法效率时，应先找出限制效率的）在优化算法效率时，应先找出限制效率的“瓶颈瓶颈”。 3 3）多数情况下，时间效率和空间效率可能是对立的，此）多数情况下，时间效率

40、和空间效率可能是对立的，此 时应分析哪个更重要，作适当折衷。时应分析哪个更重要，作适当折衷。 4 4）可考虑先选取合适的数据结构，再优化算法。）可考虑先选取合适的数据结构，再优化算法。 5 5）递归过程的实现决定了递归算法的效率往往很低，费）递归过程的实现决定了递归算法的效率往往很低，费 时和费内存空间。在解决问题时，如果能用递推法时和费内存空间。在解决问题时，如果能用递推法解解 决的，应考虑用递推法，其效率更高些。决的，应考虑用递推法，其效率更高些。 6 6）注意多用数学知识，可以大大提高算法效率。）注意多用数学知识，可以大大提高算法效率。 7 7）细节上的问题）细节上的问题, ,如如: :

41、乘、除运算效率比乘、除运算效率比加、减运算低。加、减运算低。 554 Recurrences（递归算法效率分析）（递归算法效率分析）How to obtain asymptotic “” or “O” bounds on the recurrence solution?lSubstitution method ( (置换法置换法) ) : guesses a bound and then use mathematical induction to prove our guess correct.lIteration method ( (迭代法迭代法) ) : converts the recu

42、rrence into a summation and then relies on techniques for bounding summations to solve the recurrence. lRecursion-tree method ( a kind of iteration method )lMaster method ( (主方法，母函数法主方法，母函数法) ) : provides bounds for recurrences of the form T(n) = aT(n/b)+f(n), where a 1, b 1, and f(n) is a given fun

43、ction.56In practice, we neglect certain technical details when we state and solve recurrences. ( (忽略技术细节忽略技术细节) ) 1) Assumption of integer arguments to functionsuNormally, T(n) is only defined when n is an integeruExample, the worst-case running time of MERGE-SORTTechnicalities(1) , if =1,( ) (4.2)(

44、/ 2 )(/ 2 )( ) , if 1,nT nTnTnnn572) Ignore boundary conditionsuOmit statements of the boundary conditions of recurrences, assume that T(n) is constant for small n , that is T(n) = (1) for sufficiently small n. （n 较小时，较小时，T(n)为常数）为常数）uExample, state recurrence (4.1) as T(n) = 2T(n/2) +(n),( Omit T(1

45、)=(1) ) (4.3)without explicitly giving values for small n. nThe reason is that although changing the value of T(1) changes the solution to the recurrence, the order of growth is unchanged.（改变边界值，可（改变边界值，可能改变递归式的解，但不改变解的函数增长率）能改变递归式的解，但不改变解的函数增长率）Technicalities1 , if 1 ( ) (4.1)2 ( /2) , if 1 nT nT n

46、nn58neglect certain technical details1) Assumption of integer arguments to functions2) Ignore boundary conditions3) Omit floors, ceilingslThese details dont affect the asymptotic bounds of many recurrences encountered in the analysis of algorithms （忽略细节不会影响算法的渐近分（忽略细节不会影响算法的渐近分析）析）Technicalities59Ke

47、y points1) guessing the form of the solution;2) using mathematical induction to show the solution works.4.1 The substitution method1 , if 1,Example: ( )2 ( /2), if 1.nT nT nnn(1) Guess: ( )lg(2) Induction : 1lg1( ) : Inductive hypothesis is that ( )lg for all . Use the inductive hypothesis of ( /2)

48、to prove ( ) T nnnnnnnnT nT kkkkknT nT n BasicInductive step ( ) = 2 ( /2) = 2( /2)lg( /2)( /2) (by inductive hypothesis) = lg( /2) (lglg2)2 = lg.T nT nnnnnnnnnnnnnnnn60Key points1)guessing the form of the solution;2)using mathematical induction to show the solution works.4.1 The substitution method

49、1 , if 1,Example: ( )2 ( /2), if 1.nT nT nnn(1) Guess: ( )lg(2) Induction : 1lg1( ) : Inductive hypothesis is that ( )lg for all . Use the inductive hypothesis of ( /2) to prove ( ).T nnnnnnnnT nT kkkkknT nT n BasicInductive steplThe method is powerful, but it can be applied only in cases when it is

50、 easy to guess the form of the answer. 61lThe substitution method can be used to establish either upper ( O ) or lower bounds () on a recurrence.lexample, determining an upper bound on the recurrence (4.4)(1) Guessing that the solution is T(n) = O(n lg n).(2) Proving T(n)cn lg n for a some constant

51、c 0.uAssume that this bound holds for n/2 , that is, that . Substituting into the recurrence yields where the last step holds as long as c 1.4.1 The substitution method( )2 ( /2 ),T nTnn(/2 )/2 lg(/2 )Tnc nn( ) =2 (/2 )2(/2 lg( /2 ) lg( /2) = lglg2 lg lg ,T nTnnc nnncnnncnncnncnncnncnn62lMathematica

52、l induction now requires us to show that our solution holds for the boundary conditions. lTypically, the boundary conditions are suitable as base cases for the inductive proof.lThis requirement can sometimes lead to problems.lAssume that T(1) = 1 is the sole boundary condition of the recurrence. The

53、n, we cant choose c large enough, since T(1)c 1 lg 1 = 0, which is at odds with T(1)=1. The case of our inductive proof fails to hold.（递归结果与初始情况矛（递归结果与初始情况矛盾，即递归证明失败？）盾，即递归证明失败？）4.1 The substitution method( )2 ( /2 ), (4.4)T nTnn( )( lg ) , ( ) lgT nO nnT nc nn63lAn inductive hypothesis inconsistent

54、 with specific boundary condition, How to overcome the difficulty?（如何克服递归结果与边界条件不一致的问题？）（如何克服递归结果与边界条件不一致的问题？）uasymptotic notation only requires us to prove T(n)cnlg n for n n0, where n0 is a constant.uto remove the difficult boundary condition T(1) = 1uImpose T(2) and T(3) as boundary conditions fo

55、r the inductive proof.uFrom the recurrence, we derive T(2) = 4 and T(3) = 5.uThe inductive proof that T(n)cn lg n can now be completed by choosing any c2 so that T(2)c2 lg 2 and T(3)c 3 lg 3.To extend boundary conditions( )2 ( /2 ) ; ( )( lg ) , ( ) lgT nTnnT nO nnT nc nn64lUnfortunately, there is n

56、o general way to guess the correct solutions to recurrences. ( (猜想不是一种方法猜想不是一种方法) )lGuessing a solution takes experience and, occasionally, creativity.( why we study the course? Its a training for us to get experience, to catch occasion, to have creativity. )lFortunately, though, there are some heur

57、istics (recursion tress) that can help you become a good guesser. 4.1.1 Making a good guess65lIf a recurrence is similar to one you have seen before, then guessing a similar solution is reasonable. For example, uwhich looks difficult because of the added “17”.uIntuitively, this additional term canno

58、t substantially affect the solution to the recurrence.（该附加项不会（该附加项不会从本质上影响递归解）从本质上影响递归解）uWhen n is large, the difference between T( n/2 ) and T( n/2 + 17) is not that large. Consequently, we make the guess that T(n) = O(n lg n), which you can verify as correct by using the substitution method.4.1.1

59、Making a good guess( )2 (/217),T nTnn66lAnother way to make a good guess is to prove loose upper and lower bounds on the recurrence and then reduce the range of uncertainty. （寻找松的上、下渐近界，范围缩小，逐步逼近）（寻找松的上、下渐近界，范围缩小，逐步逼近）For exampleuwe might start with a lower bound of T(n) =(n), since we have the term

60、 n in the recurrence,uand we can prove an initial upper bound T(n) = O(n2).uThen, we can gradually lower the upper bound and raise the lower bound until we converge on the correct, asymptotically tight solution of T(n)=(nlgn).4.1.1 Making a good guess( )2 ( /2 ) (4.4)T nTnn67lSometimes, guess correc