算法设计：第六讲-2013

1、递归树法和主方法主方法（Master Method）：主项定理也就是对递归树方法的一种归纳，从而形成了固定的计算方式，可以分为三种情形来计算。T(n)=aT(n/b)+f(n) 这三种情形主要是比较 与 f(n) nlogba递归树法和主方法为什么要比较这两个函数呢？观察原式，可以看出， 其实相当于用递归树方法解出的递归方程的右侧的第一项。而f(n)则是递归方程的右侧的第二项。这样，主项定理实际上是在比较组成结果的两个函数项，而且这种比较是按照数量级（或者说是变化幅度）来比较的，也就是说，如2n 与 28n是数量级（变化幅度）相当的。 nlogba递归树法和主方法这样就有了三种不同的情形：CA

2、SE 1： f(n) 0为任意小的常数或者说，f(n) 比 变化的慢，慢n 那么，T(n) = ( )nlogbanlogbanlogbanlogba递归树法和主方法CASE 2： f(n) = 也就是 f(n) = ( ) 或者说，f(n) 和 变化一样快，即这两项的数量级相当那么，T(n) = ( logn )nlogbanlogbanlogbanlogba递归树法和主方法情形3： f(n) 也就是 f(n) = ( + ) ， 0为任意小的常数或者说，f(n) 比 变化快，快n。且能够找到某常数c1，对充分大的正整数n有af(n/b)cf(n) 那么，T(n) = (f(n) )nlog

3、banlogbanlogba正规性条件：含义是a个子间题的再分解和再综合所需要的时间最多与原问题的分解和综合所需要的时间同阶。 递归树法和主方法练习：（1）T(n)=5T(n/2)+ (n2)（2）T(n)=2T(n/2)+ (n)（3）T(n)=5T(n/2)+(n3) 注意事项三种情况没有覆盖所有可能的f(n)case 1和case 2之间存在一条“沟“，即f(n)小于但不是多项式地小于nlogba T(n)=4T(n/2)+n2/logn 主方法对该递归方程不适用。因为a=4,b=2,f(n)=n2/logn,该递归方程处于主方法case1和case2之间注意事项同样地， case 2和

4、case 3之间存在一条“沟“，即f(n)大于但不是多项式地大于nlogba T(n)=2T(n/2)+nlogn 主方法对该递归方程不适用。因为a=2,b=2,nlogba=n,但是f(n)/nlogba=logn渐进小于n ,对任意正常数该递归方程处于主方法cas2和case3之间若f(n)落入上述两条”沟“，或者case3中的正规性条件不能满足时，主方法就不能用来解递归式递归树法和主方法举例：（1）T(n)=9T(n/3)+n（2）T(n)=T(2n/3)+1（3）T(n)=3T(n/4)+nlogn 递归树法和主方法快速排序的时间复杂度分析算法设计过程演示复杂度分析第三章 算法设计工具

5、和优化技巧算法设计的基础工作：把人脑思维出的解决问题的方法、步骤，规范化地描述成“机械化的操作”。程序设计语言提供的“机械化的操作”很少：计算、输入、输出流程控制：选择、循环、函数调用（递归）存储模式：变量、数组、结构体和文件本章内容：利用这些基本的“机械化操作”设计高质量的算法。3.1 循环与递归计算机在进行数据的“机械化的重复操作”时，必须设计出表现形式不变，但能实现动态处理数据的重复操作。即：循环条件、循环体的语句是“不变的”。处理的数据是变化的3.1.1 循环设计要点循环设计中要注意算法的效率【例题1】求 1/1!-1/3!+1/5!-1/7!+（-1）n+1/(2n-1)!问题分析：

6、此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。数学模型1：Sn=Sn-1+（-1）n+1/(2n-1)!算法设计1：以上算法是二重循环来完成 ，但算法的效率却太低是O（n2）。3.1.1 循环设计要点数学模型2： Sn=Sn-1+（-1）n+1An； An=An-1 *1/(2*n-2)*(2*n-1)算法设计2：按照数学模型2，只需一重循环就能解决问题，法的时间复杂性为O（n）。结论：构造循环时，一定要考虑算法的效率，尽量减少循环的重数与循环次数。 3.1.1 循环设计要点“自顶向下”的设计方法：自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的

7、过程。 “自顶向下”设计的步骤：对问题进行仔细分析，写出程序运行的主要过程和任务从大的功能方面把一个问题的解决过程分为几个问题，每个子问题形成一个模块。3.1.1 循环设计要点“自顶向下”设计的特点：先整体后局部，先抽象后具体【例题2】编算法找出1000以内所有完数。例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28 its factors are 1 2 4 7 14。3.1.1 循环设计要点设计过程：（1）顶层算法for(i=1;i=1000;i=i+1) 判断i是否是完数; 是完数则按照

8、格式输出; 3.1.1 循环设计要点（2）判断i是否是“完数”（3）进一步细化，判断i是否为完数for(j=1;ji;j=j+1) 找i的因子，并进行累加;若累加和等于i，则按照格式输出i;s=1;for(j=2;ji;j=j+1) if(i%j=0) s+=j;if(s=i) 按照格式输出i;3.1.1 循环设计要点（4）考虑输出格式，存在两个问题：因为需要输出每个因子，因此需要借助数组记录每个因子，其值是在找因子的过程中产生。假设使用int a100;必须知道因子的个数：假设为k，其值也是在找因子的过程中产生。printf(“%d Its factors are:”);for(i=0;ik

9、;i=i+1) printf(“%5d”,ai);3.1.1 循环设计要点（5）进一步细化算法：s=1;k=0;for(j=2;ji;j=j+1) if(i%j=0) s+=j; ak=j; k+;if(s=i) 按照格式输出i;算法描述3.1.1 循环设计要点【例题3】求一个矩阵（nn）的鞍点(即在行上最小而在列上最大的点)。 （1）顶层算法 for(i=0;in;i=i+1) 找第i行上最小的元素t并记录所在列minj; 检验t是否第minj列的最大值， 满足则ai,minj是鞍点;3.1.1 循环设计要点（2）找第i行上最小的元素t及所在列minj t=ai0; minj=0;for(j

10、=1;jn;j=j+1) if(aijt) t=aij; minj=j;3.1.1 循环设计要点（3）检验t是否是minj 列的最大值：for(k=0;kt) break;if(k=n) print(“a“,i,“”,minj,“=”,t);3.1.1 循环设计要点（4）细化：考虑到没有鞍点的情况，所以设计一个计数器（count）统计鞍点的数目。for(k=0;kt) break;if(k=n) print(“a“,i,“”,minj,“=”,t); count+; 算法描述3.1.1 循环设计要点由具体到抽象设计循环结构：对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一

11、个由具体到抽象设计循环细节的例题。【例4】编写算法：打印具有下面规律的图形。 1 5 2 8 6 3 10 9 7 43.1.1 循环设计要点【算法设计】（1）容易发现图形中自然数在矩阵中排列的规律，题目中1，2，3，4所在位置我们称为第1层（主对角线），图中5，6，7所在位置我们称为第二层。一般地，（2）第一层有n个元素，第二层有n-1个元素，第i层有n+i-1个元素。3.1.1 循环设计要点（3）基于以上数据变化规律A、以层号作为外层循环，循环变量为i（范围为1n）；B、以层内元素从左上到右下的序号作为内循环，循环变量为j（范围为1n+i-1）。C、这样循环的执行过程正好与“摆放”自然数的

12、顺序相同。D、下面的问题就是怎么样将数据存储到对应的数组元素。3.1.1 循环设计要点（4）由具体的实例模拟摆放过程A、数组元素的存取，只能是按行、列号操作的。B、找出数组元素的行下标、列下标与层号i及层内序号j的关系：每层内元素在数组中的列下标都与其所在层内的序号j是相同的。3.1.1 循环设计要点元素的行下标i与其所在的层号及层内的序号j均有关系,具体地： 第一层：行下标与j同； 第二层：行下标比j大1； 第三层：行下标比j大2； 第i层：行下标比j大i-13.1.1 循环设计要点（5）抽象：第i层的第j个位置对应的数组元素是： aj+i-1j k=1;for(i=1;i=n;i+) for(j=1;jn) （3）Q(1,m)=Q(1,1)=1 (n=1)3.1.2 递归设计要点（4）Q(n,n)=1+Q(n,n-1) （m=n）Q(n,n-1)表示n的所有其他分划，即最大被加数m=n-1的划分。（5）Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn) Q(n,m-1)表示被加数中不包含m的分划的数目； Q(n-m,m)表示被加数中包含(注意不是小于)m的分划的数目，算法如下：Divinteger(n, m)