算法分析复习资料.ppt
1.算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、能行性和、能行性和 。2.算法分析时通常只考虑三种情况下的时间复杂性，实践表明可操作性最好且最有算法分析时通常只考虑三种情况下的时间复杂性，实践表明可操作性最好且最有实用价值的是实用价值的是 情况下的时间复杂性。情况下的时间复杂性。3.将复杂问题按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同将复杂问题按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题进而求解的方法称为的子问题进而求解的方法称为 法。法。4.利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这种算法称为种算法称为 法。法。5.动态规划算法的两个基本要素是动态规划算法的两个基本要素是 和和 。6.在解决最优化问题的求解过程中，采用一种局部最优策略，把问题范围和规模缩在解决最优化问题的求解过程中，采用一种局部最优策略，把问题范围和规模缩小，最后把每一步的结果合并起来得到一个全局最优解，这种算法称为小，最后把每一步的结果合并起来得到一个全局最优解，这种算法称为 法。法。7.法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树树8.法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树树1、请回答：什么是算法请回答：什么是算法？算法？算法应具有哪些重要特性应具有哪些重要特性？2、阐述算法与程序的联系与区别阐述算法与程序的联系与区别。3、影响影响一个程序运行时间的因素有哪些？一个程序运行时间的因素有哪些？4、简述贪心算法的思想策略、算法特点，以及它所具有的两、简述贪心算法的思想策略、算法特点，以及它所具有的两种性质各是什么？种性质各是什么？5、简要说明贪心算法的两个基本要素。简要说明贪心算法的两个基本要素。6、请请说明回溯法和分支限界法的不同之处。说明回溯法和分支限界法的不同之处。7、设计设计一个动态规划算法，一个动态规划算法，通常通常采用的步骤有哪些？采用的步骤有哪些？渐近时间复杂度渐近时间复杂度渐近时间复杂度渐近时间复杂度 使用使用O、o等等记号表示的算法时间复杂度函记号表示的算法时间复杂度函数的数量级别，称为数的数量级别，称为算法的渐近时间复杂度算法的渐近时间复杂度算法的渐近时间复杂度算法的渐近时间复杂度2.2.1 大大O记号记号定义定义定义定义2-12-1 设设函函数数f(n)和和g(n)是是定定义义在在非非负负整整数数集集合合上上的的正正函函数数，如如果果存存在在两两个个正正常常数数c和和n0，使使得得当当nn0时时，有有f(n)cg(n)，则则称称当当n充充分分大大时时，函函数数f(n)上上有有界界，且且g(n)是是它它的的一一个个上上界界。也也可可以以说说f(n)的的阶阶不不高高于于g(n)的的阶阶。记记做做f(n)=O(g(n)，称称为为大大O记记号号（big Oh notation）。）。2.2.2 记号记号定义定义定义定义2-22-2 设设有有函函数数f(n)和和g(n)是是定定义义在在非非负负整整数数集集合合上上的的正正函函数数，如如果果存存在在两两个个正正常常数数 c和和n0，使使得得当当nn0时时，有有f(n)cg(n)，则则称称当当n充充分分大大时时，函函数数f(n)下下有有界界，且且g(n)是是它它的的一一个个下下界界。也也可可以以说说f(n)的的阶阶不不低低于于g(n)的的阶阶。记记做做f(n)=(g(n)，称称为为 记记记记号号号号（omega notation）。）。2.2.3 记号记号定义定义定义定义2-3 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 1 g g(n n)f f(n n)c c2 2 g g(n n)，则则记记做做f f(n n)=(g g(n n)，称为，称为 记号（记号（Theta notationTheta notation）。）。(g(n)代表一类函数，表示所有与代表一类函数，表示所有与g(n)增长阶数相同增长阶数相同的函数。的函数。如果一个算法的时间复杂度如果一个算法的时间复杂度f(n)=(g(n)，说明当，说明当n足足够大时，该算法的运行时间大约为够大时，该算法的运行时间大约为g(n)的某个常数倍。的某个常数倍。证明：证明：(1)f(n)=20n+logn,g(n)=n+log(1)f(n)=20n+logn,g(n)=n+log3 3n n确定函数确定函数确定函数确定函数f(n)f(n)f(n)f(n)和和和和g(n)g(n)g(n)g(n)的渐进关系（用的渐进关系（用的渐进关系（用的渐进关系（用O O O O、表示）表示）表示）表示）(2)f(n)=n(2)f(n)=n2 2/logn,g(n)=nlog/logn,g(n)=nlog2 2n n练习练习1、求函数的渐进表达式、求函数的渐进表达式（1）3n2+10n（2）n2/10+2n（3）21+1/n（4）logn3（5）10log3n2 2、确定函数、确定函数、确定函数、确定函数f(n)f(n)和和和和g(n)g(n)的渐进关系（用的渐进关系（用的渐进关系（用的渐进关系（用OO、表表表表示）示）示）示）（1 1）f(n)=lognf(n)=logn2 2;g(n)=log(n+5);g(n)=log(n+5)（）（2 2）f(n)=lognf(n)=logn2 2;g(n)=n;g(n)=n1/2 1/2（OO）（3 3）f(n)=n;g(n)=logf(n)=n;g(n)=log2 2n n（OO）（4 4）f(n)=nlogn+n;g(n)=logn f(n)=nlogn+n;g(n)=logn（）（5 5）f(n)=10;g(n)=log10 f(n)=10;g(n)=log10（）（6 6）f(n)=logf(n)=log2 2n;g(n)=logn n;g(n)=logn（）（7 7）f(n)=2f(n)=2n n;g(n)=100n;g(n)=100n2 2 （）（8 8）f(n)=2f(n)=2n n;g(n)=3;g(n)=3n n（OO）（9 9）f(n)=20n+logn,g(n)=n+logf(n)=20n+logn,g(n)=n+log3 3n n（OO）贪心法（贪心法（P120 6-1）一、背包问题。一、背包问题。n=5,m=11,(p0p4)=(8,6,15,6,3)(w0w5)=(2,3,5,2,3),最优量度标准：优先选择单位重量收益最大的最优量度标准：优先选择单位重量收益最大的物品放入背包。物品放入背包。(p0/w0,p1/w1,p2/w2,p3/w3,p4/w4)=(4,2,3,3,1)最优解为：最优解为：(x0,x1,x2,x3,x4,x5,x6)=(1,2/3,1,1,0)最大收益为最大收益为:8+6*2/3+15+6)=33lD0=0,S0=-1 l扩展0，1,2,3，D1=2,S1=0，D2=8,S2=0,D3=5,S3=0 l扩展1，2,3,4，D2=min8,2+3=5，S2=1，D4=5,S4=1l扩展2，3,4,5，D5=D2+4=9,S5=2 l扩展3，4,5，D5=min9,D3+6=9，S5=2，D6=D3+9=14，S6=3l扩展4：5，D5=min9,D4+5=9，S5=2，D6=min14,D4+7=12，S6=4l扩展5：，D6=min12,D5+2=11，S6=5最短路径为：最短路径为：0-1-2-5-60-1-2-5-6最短路径长度为最短路径长度为1111 013524628569273435分枝限界法分枝限界法动态规划法（动态规划法（P159 7-5）设设设设4 4个矩阵连乘积个矩阵连乘积个矩阵连乘积个矩阵连乘积A0 A1 A2 A3A0 A1 A2 A3，设它们的维数分别，设它们的维数分别，设它们的维数分别，设它们的维数分别为为为为A0:20A0:20 10 A1:1010 A1:10 8,A2:88,A2:8 5,A3:55,A3:5 4040。矩阵连。矩阵连。矩阵连。矩阵连乘乘乘乘AiAi+1AjAiAi+1Aj简记为简记为简记为简记为Ai:jAi:j，mijmij表示表示表示表示AiAi+1AjAiAi+1Aj最少计算量，最少计算量，最少计算量，最少计算量，sijsij表示表示表示表示AiAi+1AjAiAi+1Aj最少计算量的断最少计算量的断最少计算量的断最少计算量的断开点。采用动态规划法确定矩阵连乘积的最优计算开点。采用动态规划法确定矩阵连乘积的最优计算开点。采用动态规划法确定矩阵连乘积的最优计算开点。采用动态规划法确定矩阵连乘积的最优计算次序。要求写出计算最优解的递推关系式、递推运次序。要求写出计算最优解的递推关系式、递推运次序。要求写出计算最优解的递推关系式、递推运次序。要求写出计算最优解的递推关系式、递推运算过程和完全加括号的矩阵运算表达式。算过程和完全加括号的矩阵运算表达式。算过程和完全加括号的矩阵运算表达式。算过程和完全加括号的矩阵运算表达式。（1）递推关系式）递推关系式（2 2）p0=20,p1=10,p2=8,p3=5,p4=40,p0=20,p1=10,p2=8,p3=5,p4=40,mii=0 mii=0，sii=isii=i，i=0,1,2,3;i=0,1,2,3;m01=minm00+m11+20*10*8=1600 m01=minm00+m11+20*10*8=1600，s01=0s01=0；m12=minm11+m22+10*8*5=400m12=minm11+m22+10*8*5=400，s12=1s12=1；m23=minm22+m33+8*5*40=1600m23=minm22+m33+8*5*40=1600，s23=2s23=2；0 01 12 23 30 00 0160016001 10 04004002 20 0160016003 30 00 01 12 23 30 00 00 01 11 11 12 22 22 23 33 3（2 2）p0=20,p1=10,p2=8,p3=5,p4=40,p0=20,p1=10,p2=8,p3=5,p4=40,m02=minm00+m12+20*10*5,m01+m22+20*8*5,m02=minm00+m12+20*10*5,m01+m22+20*8*5,=min400+1000,1600+800=1400 =min400+1000,1600+800=1400，s02=0 s02=0；m13=minm11+m23+10*8*40,m12+m13=minm11+m23+10*8*40,m12+m33+10*5*40,m33+10*5*40,=min1600+3200,400+2000=2400 =min1600+3200,400+2000=2400，s13=2 s13=2；m03=minm00+m13+20*10*40,m03=minm00+m13+20*10*40,m01+m23+20*8*40,m01+m23+20*8*40,m02+m33+20*5*40 m02+m33+20*5*40 =min2400+8000,1600+1600+6400,1400+4000=5400 =min2400+8000,1600+1600+6400,1400+4000=5400，s03=2s03=20 01 12 23 30 00 01600160014001400540054001 10 0400400240024002 20 0160016003 30 00 01 12 23 30 00 00 00 02 21 11 11 12 22 22 22 23 33 3(3)(3)完全加括号的形式：（完全加括号的形式：（完全加括号的形式：（完全加括号的形式：（A0 A0（A1 A2 A1 A2）A3 A3）分治法分治法程序填空程序填空递推关系式递推关系式时间复杂度时间复杂度
