算法分析复习详解优秀PPT.ppt
1.1.算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、能行性和、能行性和、能行性和、能行性和 。2.2.算法分析时通常只考虑三种状况下的时间困难性，实践表明可操作性最好且最有算法分析时通常只考虑三种状况下的时间困难性，实践表明可操作性最好且最有算法分析时通常只考虑三种状况下的时间困难性，实践表明可操作性最好且最有算法分析时通常只考虑三种状况下的时间困难性，实践表明可操作性最好且最有好用价值的是好用价值的是好用价值的是好用价值的是 状况下的时间困难性。状况下的时间困难性。状况下的时间困难性。状况下的时间困难性。3.3.将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题进而求解的方法称为的子问题进而求解的方法称为的子问题进而求解的方法称为的子问题进而求解的方法称为 法。法。法。法。4.4.利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这种算法称为种算法称为种算法称为种算法称为 法。法。法。法。5.5.动态规划算法的两个基本要素是动态规划算法的两个基本要素是动态规划算法的两个基本要素是动态规划算法的两个基本要素是 和和和和 。6.6.在解决最优化问题的求解过程中，接受一种局部最优策略，把问题范围和规模缩在解决最优化问题的求解过程中，接受一种局部最优策略，把问题范围和规模缩在解决最优化问题的求解过程中，接受一种局部最优策略，把问题范围和规模缩在解决最优化问题的求解过程中，接受一种局部最优策略，把问题范围和规模缩小，最终把每一步的结果合并起来得到一个全局最优解，这种算法称为小，最终把每一步的结果合并起来得到一个全局最优解，这种算法称为小，最终把每一步的结果合并起来得到一个全局最优解，这种算法称为小，最终把每一步的结果合并起来得到一个全局最优解，这种算法称为 法。法。法。法。7.7.法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树8.8.法在问题的解空间树中，按广度优先策略，从根结点动身搜寻解空间树法在问题的解空间树中，按广度优先策略，从根结点动身搜寻解空间树法在问题的解空间树中，按广度优先策略，从根结点动身搜寻解空间树法在问题的解空间树中，按广度优先策略，从根结点动身搜寻解空间树1 1、请回答：什么是算法？算法应具有哪些重要特性？、请回答：什么是算法？算法应具有哪些重要特性？、请回答：什么是算法？算法应具有哪些重要特性？、请回答：什么是算法？算法应具有哪些重要特性？2 2、阐述算法与程序的联系与区分。、阐述算法与程序的联系与区分。、阐述算法与程序的联系与区分。、阐述算法与程序的联系与区分。3 3、影响一个程序运行时间的因素有哪些？、影响一个程序运行时间的因素有哪些？、影响一个程序运行时间的因素有哪些？、影响一个程序运行时间的因素有哪些？4 4、简述贪心算法的思想策略、算法特点，以及它所具有的两、简述贪心算法的思想策略、算法特点，以及它所具有的两、简述贪心算法的思想策略、算法特点，以及它所具有的两、简述贪心算法的思想策略、算法特点，以及它所具有的两种性质各是什么？种性质各是什么？种性质各是什么？种性质各是什么？5 5、简要说明贪心算法的两个基本要素。、简要说明贪心算法的两个基本要素。、简要说明贪心算法的两个基本要素。、简要说明贪心算法的两个基本要素。6 6、请说明回溯法和分支限界法的不同之处。、请说明回溯法和分支限界法的不同之处。、请说明回溯法和分支限界法的不同之处。、请说明回溯法和分支限界法的不同之处。7 7、设计一个动态规划算法，通常接受的步骤有哪些？、设计一个动态规划算法，通常接受的步骤有哪些？、设计一个动态规划算法，通常接受的步骤有哪些？、设计一个动态规划算法，通常接受的步骤有哪些？渐近时间困难度渐近时间困难度渐近时间困难度渐近时间困难度 运用运用运用运用OO、o o等记号表示的算法时间困难度等记号表示的算法时间困难度等记号表示的算法时间困难度等记号表示的算法时间困难度函数的数量级别，称为算法的渐近时间困难度函数的数量级别，称为算法的渐近时间困难度函数的数量级别，称为算法的渐近时间困难度函数的数量级别，称为算法的渐近时间困难度2.2.1 大大O记号记号定义定义定义定义2-1 2-1 设设设设函函函函数数数数f(n)f(n)和和和和g(n)g(n)是是是是定定定定义义义义在在在在非非非非负负负负整整整整数数数数集集集集合合合合上上上上的的的的正正正正函函函函数数数数，假假假假如如如如存存存存在在在在两两两两个个个个正正正正常常常常数数数数c c和和和和n0n0，使使使使得得得得当当当当nn0nn0时时时时，有有有有f(n)cg(n)f(n)cg(n)，则则则则称称称称当当当当n n充充充充分分分分大大大大时时时时，函函函函数数数数f(n)f(n)上上上上有有有有界界界界，且且且且g(n)g(n)是是是是它它它它的的的的一一一一个个个个上上上上界界界界。也也也也可可可可以以以以说说说说f(n)f(n)的的的的阶阶阶阶不不不不高高高高于于于于g(n)g(n)的的的的阶阶阶阶。记记记记做做做做f(n)f(n)=O(g(n)O(g(n)，称称称称为为为为大大大大OO记记记记号号号号（big big Oh Oh notationnotation）。）。）。）。2.2.2 记号记号定义定义定义定义2-2 2-2 设设设设有有有有函函函函数数数数f(n)f(n)和和和和g(n)g(n)是是是是定定定定义义义义在在在在非非非非负负负负整整整整数数数数集集集集合合合合上上上上的的的的正正正正函函函函数数数数，假假假假如如如如存存存存在在在在两两两两个个个个正正正正常常常常数数数数 c c和和和和n0n0，使使使使得得得得当当当当nn0nn0时时时时，有有有有f(n)cg(n)f(n)cg(n)，则则则则称称称称当当当当n n充充充充分分分分大大大大时时时时，函函函函数数数数f(n)f(n)下下下下有有有有界界界界，且且且且g(n)g(n)是是是是它它它它的的的的一一一一个个个个下下下下界界界界。也也也也可可可可以以以以说说说说f(n)f(n)的的的的阶阶阶阶不不不不低低低低于于于于g(n)g(n)的的的的阶阶阶阶。记记记记做做做做f(n)f(n)=(g(n)(g(n)，称称称称为为为为 记记记记号号号号（omega omega notationnotation）。）。）。）。2.2.3 记号记号定义定义定义定义2-3 2-3 2-3 2-3 设有函数设有函数设有函数设有函数f(n)f(n)f(n)f(n)和和和和g(n)g(n)g(n)g(n)是定义在非负整数集合上是定义在非负整数集合上是定义在非负整数集合上是定义在非负整数集合上的正函数，假如存在正常数的正函数，假如存在正常数的正函数，假如存在正常数的正函数，假如存在正常数c1c1c1c1，c2c2c2c2和和和和n0n0n0n0，使得当，使得当，使得当，使得当nn0nn0nn0nn0时，有时，有时，有时，有c1 g(n)f(n)c2 g(n)c1 g(n)f(n)c2 g(n)c1 g(n)f(n)c2 g(n)c1 g(n)f(n)c2 g(n)，则记做，则记做，则记做，则记做f(n)=f(n)=f(n)=f(n)=(g(n)(g(n)(g(n)(g(n)，称为，称为，称为，称为记号（记号（记号（记号（Theta Theta Theta Theta notationnotationnotationnotation）。）。）。）。(g(n)(g(n)代表一类函数，表示全部与代表一类函数，表示全部与代表一类函数，表示全部与代表一类函数，表示全部与g(n)g(n)增长阶数相同增长阶数相同增长阶数相同增长阶数相同的函数。的函数。的函数。的函数。假如一个算法的时间困难度假如一个算法的时间困难度假如一个算法的时间困难度假如一个算法的时间困难度f(n)=f(n)=(g(n)(g(n)，说明当，说明当，说明当，说明当n n足足足足够大时，该算法的运行时间大约为够大时，该算法的运行时间大约为够大时，该算法的运行时间大约为够大时，该算法的运行时间大约为g(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)=33l lD0=0,S0=-1 D0=0,S0=-1 l l扩展扩展0 0，1,2,31,2,3，D1=2,S1=0D1=2,S1=0，D2=8,S2=0,D3=5,S3=0 D2=8,S2=0,D3=5,S3=0 l l扩展扩展1 1，2,3,42,3,4，D2=min8,2+3=5D2=min8,2+3=5，S2=1S2=1，D4=5,S4=1D4=5,S4=1l l扩展扩展2 2，3,4,53,4,5，D5=D2+4=9,S5=2 D5=D2+4=9,S5=2 l l扩展扩展3 3，4,54,5，D5=min9,D3+6=9D5=min9,D3+6=9，S5=2S5=2，D6=D3+9=14D6=D3+9=14，S6=3S6=3l l扩展扩展4 4：55，D5=min9,D4+5=9D5=min9,D4+5=9，S5=2S5=2，D6=min14,D4+7=12D6=min14,D4+7=12，S6=4S6=4l l扩展扩展5 5：，D6=min12,D5+2=11D6=min12,D5+2=11，S6=5S6=5最短路径为：最短路径为：最短路径为：最短路径为：0-1-2-5-60-1-2-5-60-1-2-5-60-1-2-5-6最短路径长度为最短路径长度为最短路径长度为最短路径长度为11111111 0 01 13 35 52 24 46 62 28 85 56 69 92 27 73 34 43 35 5分枝限界法分枝限界法动态规划法（动态规划法（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）分治法分治法程序填空程序填空递推关系式递推关系式时间困难度时间困难度
