算法分析复习详解优秀PPT.ppt
《算法分析复习详解优秀PPT.ppt》由会员分享,可在线阅读,更多相关《算法分析复习详解优秀PPT.ppt(17页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1.1.算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、算法的五个基本特征包括输入、输出、能行性和、能行性和、能行性和、能行性和 。2.2.算法分析时通常只考虑三种状况下的时间困难性,实践表明可操作性最好且最有算法分析时通常只考虑三种状况下的时间困难性,实践表明可操作性最好且最有算法分析时通常只考虑三种状况下的时间困难性,实践表明可操作性最好且最有算法分析时通常只考虑三种状况下的时间困难性,实践表明可操作性最好且最有好用价值的是好用价值的是好用价值的是好用价值的是 状况下的时间困难性。状况下的时间困难性。状况下的时间困难性。状况下的时间困难
2、性。3.3.将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同将困难问题依据某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题进而求解的方法称为的子问题进而求解的方法称为的子问题进而求解的方法称为的子问题进而求解的方法称为 法。法。法。法。4.4.利用最优子结构,自底向上从子问题的最优解逐步构造出整个问题的最优解,这利用最优子结构,自底向上从子问题的最优解逐步构造出整个问题的最优解,这利用最优子结构,自底向上从子问题的最优
3、解逐步构造出整个问题的最优解,这利用最优子结构,自底向上从子问题的最优解逐步构造出整个问题的最优解,这种算法称为种算法称为种算法称为种算法称为 法。法。法。法。5.5.动态规划算法的两个基本要素是动态规划算法的两个基本要素是动态规划算法的两个基本要素是动态规划算法的两个基本要素是 和和和和 。6.6.在解决最优化问题的求解过程中,接受一种局部最优策略,把问题范围和规模缩在解决最优化问题的求解过程中,接受一种局部最优策略,把问题范围和规模缩在解决最优化问题的求解过程中,接受一种局部最优策略,把问题范围和规模缩在解决最优化问题的求解过程中,接受一种局部最优策略,把问题范围和规模缩小,最终把每一步的
4、结果合并起来得到一个全局最优解,这种算法称为小,最终把每一步的结果合并起来得到一个全局最优解,这种算法称为小,最终把每一步的结果合并起来得到一个全局最优解,这种算法称为小,最终把每一步的结果合并起来得到一个全局最优解,这种算法称为 法。法。法。法。7.7.法在问题的解空间树中,按深度优先策略,从根结点动身搜寻解空间树法在问题的解空间树中,按深度优先策略,从根结点动身搜寻解空间树法在问题的解空间树中,按深度优先策略,从根结点动身搜寻解空间树法在问题的解空间树中,按深度优先策略,从根结点动身搜寻解空间树8.8.法在问题的解空间树中,按广度优先策略,从根结点动身搜寻解空间树法在问题的解空间树中,按广
5、度优先策略,从根结点动身搜寻解空间树法在问题的解空间树中,按广度优先策略,从根结点动身搜寻解空间树法在问题的解空间树中,按广度优先策略,从根结点动身搜寻解空间树1 1、请回答:什么是算法?算法应具有哪些重要特性?、请回答:什么是算法?算法应具有哪些重要特性?、请回答:什么是算法?算法应具有哪些重要特性?、请回答:什么是算法?算法应具有哪些重要特性?2 2、阐述算法与程序的联系与区分。、阐述算法与程序的联系与区分。、阐述算法与程序的联系与区分。、阐述算法与程序的联系与区分。3 3、影响一个程序运行时间的因素有哪些?、影响一个程序运行时间的因素有哪些?、影响一个程序运行时间的因素有哪些?、影响一个
6、程序运行时间的因素有哪些?4 4、简述贪心算法的思想策略、算法特点,以及它所具有的两、简述贪心算法的思想策略、算法特点,以及它所具有的两、简述贪心算法的思想策略、算法特点,以及它所具有的两、简述贪心算法的思想策略、算法特点,以及它所具有的两种性质各是什么?种性质各是什么?种性质各是什么?种性质各是什么?5 5、简要说明贪心算法的两个基本要素。、简要说明贪心算法的两个基本要素。、简要说明贪心算法的两个基本要素。、简要说明贪心算法的两个基本要素。6 6、请说明回溯法和分支限界法的不同之处。、请说明回溯法和分支限界法的不同之处。、请说明回溯法和分支限界法的不同之处。、请说明回溯法和分支限界法的不同之
7、处。7 7、设计一个动态规划算法,通常接受的步骤有哪些?、设计一个动态规划算法,通常接受的步骤有哪些?、设计一个动态规划算法,通常接受的步骤有哪些?、设计一个动态规划算法,通常接受的步骤有哪些?渐近时间困难度渐近时间困难度渐近时间困难度渐近时间困难度 运用运用运用运用OO、o o等记号表示的算法时间困难度等记号表示的算法时间困难度等记号表示的算法时间困难度等记号表示的算法时间困难度函数的数量级别,称为算法的渐近时间困难度函数的数量级别,称为算法的渐近时间困难度函数的数量级别,称为算法的渐近时间困难度函数的数量级别,称为算法的渐近时间困难度2.2.1 大大O记号记号定义定义定义定义2-1 2-1
8、 设设设设函函函函数数数数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)是是是是它它它它的的的的一一一一个个个个上上上上界界界界。也也也也可可可可以以
9、以以说说说说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)是是是是定定定定义义义义在在在在非非非非负负负负整整整整数数数数集集集集合合合合上上上上的的的的正正正正函函函函数数数数,假假假假如如如如存存存存在在在在两两两两个个个个正正正正常常常常数数数
10、数 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)。)
11、。)。)。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)c
12、2 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)增长阶数相同增长阶数相同增长阶数相同增长阶数相同的函数。的函数。的函数。的函数。假如一个算法的时间困难度假如一个算法的时间困难度假如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 复习 详解 优秀 PPT
限制150内