算法设计与分析-课件.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法设计与分析-课件.pptx》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 课件
- 资源描述:
-
1、1第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 随机化算法随机化算法算法设计与分析算法设计与分析 目录目录21.11.1 算法与程序算法与程序1.21.2 算法复杂度分析算法复杂度分析1.31.3 NPNP完全性理论完全性理论算法设计与分析算法设计与分析 第一章第一章 目录目录3“算法是任何定义好的计算程式,它取某些值算法是任何定义好的计算程式,它取某些值或值的集合作为输入,并产生某些值或值的集或值的集合作为输入,并产生某些值或值的集合
2、作为输出。合作为输出。”1.11.1 算法与程序算法与程序 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述算法算法:是将问题的输入转化为输出的一系列是将问题的输入转化为输出的一系列 计算或操作步骤计算或操作步骤.1 1 算法定义及其特性算法定义及其特性 4 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述例:求两个不全为例:求两个不全为0的非负整数的非负整数m,n的最大公约数的最大公约数 gcd(m,n)的的欧几里德算法描述欧几里德算法描述:1.如果如果n=0,返回返回m的值作为结果,过程结束;的值作为结果,过程结束;否则,进入第二步;否则,进入第二步;2.用用n
3、去除去除m,将余数赋给,将余数赋给 r;3.将将n的值赋给的值赋给m,将,将r的值赋给的值赋给n,返回第一步。返回第一步。算法描述举例5计算机算法与人工算法计算机算法与人工算法 算法概述算法概述例如例如 求定积分求定积分:s=人工处理步骤为人工处理步骤为找出找出f(x)的源函数的源函数F(x)利用牛利用牛-莱公式莱公式:s=F(b)-F(a)dxxfba)(算法设计与分析算法设计与分析 算法概述算法概述有些问题没有计算机算法有些问题没有计算机算法.有些问题计算机算法与人工算法不同有些问题计算机算法与人工算法不同.计算机算法:计算定积分采用数值积分的方计算机算法:计算定积分采用数值积分的方法法,
4、得到一个近似解得到一个近似解.6算法设计与分析算法设计与分析 算法概述算法概述算法的定义因看待的角度不同而不同算法的定义因看待的角度不同而不同哲学家:算法是解决一个问题的抽象行为哲学家:算法是解决一个问题的抽象行为序列。序列。码农:算法是一个计算过程,它接受一些码农:算法是一个计算过程,它接受一些输入,并产生某些输出。输入,并产生某些输出。高大上:算法是解决一个精确定义的计算高大上:算法是解决一个精确定义的计算问题的工具。问题的工具。核心:算法是解决问题的办法和法则,算法必核心:算法是解决问题的办法和法则,算法必须能够让人一步一步照着执行。须能够让人一步一步照着执行。7算法的特征算法的特征1.
5、1.有穷性有穷性 一个算法须在执行有限个运算步后终止一个算法须在执行有限个运算步后终止,每一步必须每一步必须在有限时间内完成在有限时间内完成.实际应用中实际应用中,算法的有穷性应该包括算法的有穷性应该包括执行时间的合理性执行时间的合理性.算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述 程序程序是算法的程序设计语言的具体实现是算法的程序设计语言的具体实现.可不满足性质可不满足性质1.1.一个算法面向一个问题,而不是仅仅求解一个问题的实例一个算法面向一个问题,而不是仅仅求解一个问题的实例 操作系统程序:是一个在无限循环中执操作系统程序:是一个在无限循环中执行的程序,而不是一个算法。
6、行的程序,而不是一个算法。8 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述例如例如 计算分段函数计算分段函数 f(x)=算法描述:输入变量算法描述:输入变量x,1 x100 0 x10若若x大于大于100的数,输出的数,输出1;若若x小于小于10的数,输出的数,输出0.输入输入10=x 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述5.5.输出输出 算法产生至少有一个输出项算法产生至少有一个输出项10 1.1.问题的陈述问题的陈述 理解问题,并用科学规范的语言把所求解问题进行准理解问题,并用科学规范的语言把所求解问题进行准确的描述确的描述,包括所有已知条件和输
7、出要求包括所有已知条件和输出要求.2.2.建立数学模型建立数学模型 通过对问题分析通过对问题分析,找出其中所有操作对象以及对象之找出其中所有操作对象以及对象之间的关系间的关系,并用数学语言加以描述并用数学语言加以描述.对非数值型解法来说对非数值型解法来说,数学模型通常是链表数学模型通常是链表,树树,图图,集合等数据结构集合等数据结构.2.2.算法设计过程算法设计过程(程序设计过程程序设计过程)算法设计与分析算法设计与分析 算法概述算法概述113.3.算法设计算法设计 根据数据模型根据数据模型,给出求解问题的一系列步骤给出求解问题的一系列步骤,且这些步骤可通过计算机的各种操作来实现且这些步骤可通
8、过计算机的各种操作来实现.4.4.算法的正确性证明算法的正确性证明 算法的正确性算法的正确性:对一切合法的输入对一切合法的输入,算法均能算法均能在有限次的计算后产生正确的输出在有限次的计算后产生正确的输出.算法设计与分析算法设计与分析 算法概述算法概述 5.5.算法的程序实现算法的程序实现 将一个算法描述正确地编写成机器语言程序将一个算法描述正确地编写成机器语言程序.12问题的求解过程问题的求解过程 算法概述算法概述6.6.算法分析算法分析 对执行该算法所消耗的计算机对执行该算法所消耗的计算机资源资源进行估进行估算算,对数值型算法还需分析算法的对数值型算法还需分析算法的稳定性稳定性和和误差误差
9、等等问题问题.计算机资源中最重要的是计算机资源中最重要的是时间和空间时间和空间资源资源,执行一个算法程序需要的时间和占用的内存空执行一个算法程序需要的时间和占用的内存空间分别称为间分别称为算法的时间复杂度和空间复杂性算法的时间复杂度和空间复杂性 .算法设计与分析算法设计与分析 算法概述算法概述13 描述算法的方式一般有三种描述算法的方式一般有三种:自然语言自然语言,流程图流程图,伪代码语言。伪代码语言。伪代码描述介于自然语言与程序伪代码描述介于自然语言与程序设计语言之间。设计语言之间。3.3.算法的描述算法的描述 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述144.算法结构算
10、法结构 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述任何算法都可由顺序结构、选择结构、循环结构这任何算法都可由顺序结构、选择结构、循环结构这三块三块“积木积木”通过组合和嵌套表达出来,遵循这种方通过组合和嵌套表达出来,遵循这种方法的程序设计,即为结构化程序设计法的程序设计,即为结构化程序设计。15数值型算法数值型算法:算法中的基本运算为算术运算算法中的基本运算为算术运算.非数值型算法非数值型算法:算法中的基本运算为逻辑运算算法中的基本运算为逻辑运算.串行算法串行算法:串行计算机上执行的算法串行计算机上执行的算法.并行算法并行算法:并行计算机上执行的算法并行计算机上执行的算法.
11、从处理方式上从处理方式上5.算法分类算法分类从解法上从解法上 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述本课程主要介绍非数值型的串行算法本课程主要介绍非数值型的串行算法.16l算法的复杂性算法的复杂性:指执行算法所消耗或占用的资指执行算法所消耗或占用的资源的数量源的数量l一个算法所需资源越多一个算法所需资源越多,我们就说它的复杂性我们就说它的复杂性越高越高,反之则低反之则低.算法复杂性分析算法复杂性分析 时间复杂性时间复杂性空间复杂性空间复杂性算法的复杂性算法的复杂性1.2 算法的复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述17考虑考虑空间复杂
12、性空间复杂性的理由的理由在多用户系统中运行时,需指明分给该程序在多用户系统中运行时,需指明分给该程序的内存大小;的内存大小;需预先知道计算机系统是否有足够的内存来需预先知道计算机系统是否有足够的内存来运行该程序;运行该程序;一个问题可能有若干个不同的内存解决方案一个问题可能有若干个不同的内存解决方案,从中择取,从中择取;用空间复杂性估计一个程序可能解决的问题用空间复杂性估计一个程序可能解决的问题的最大规模的最大规模。算法设计与分析算法设计与分析 算法概述算法概述18 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述考虑考虑时间复杂性时间复杂性的理由的
13、理由某些计算机用户需要提供程序运行时间的上限某些计算机用户需要提供程序运行时间的上限(用户可接受的);(用户可接受的);所开发的程序需要提供一个满意的实时反应。所开发的程序需要提供一个满意的实时反应。19 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述算法分析:(渐进算法分析):对执行算法所消对执行算法所消耗或占用的资源进行估算耗或占用的资源进行估算,给出算法耗费的给出算法耗费的限界函数限界函数.需解决两个问题需解决两个问题:如何度量复杂性如何度量复杂性?如何分析复杂性如何分析复杂性?20 算法的复杂性算法的复杂性:算法运行所需的时间和空间的数量算
14、法运行所需的时间和空间的数量.它与算法求解问题的问题的规模规模n n,算法的输入数输入数I 及算法本身算法本身有关.例如例如 在数组中找分量在数组中找分量c,n:数组中分量的个数数组中分量的个数 两个矩阵相乘两个矩阵相乘,n:矩阵的维数矩阵的维数 表中排序表中排序,n:数组中分量的个数数组中分量的个数 遍历一棵树遍历一棵树,n:树中节点数树中节点数1.复杂性的计量 算法复杂性分析算法复杂性分析问题的规模问题的规模n:指问题的输入数据或初始数据的量指问题的输入数据或初始数据的量.在不同的问题中在不同的问题中,n有不同的表现形式:有不同的表现形式:复杂性的计量复杂性的计量 算法概述算法概述算法设计
15、与分析算法设计与分析 算法概述算法概述21算法设计与分析算法设计与分析 算法概述算法概述 算法效率与计算机的性能有关,但此因素对所有算法算法效率与计算机的性能有关,但此因素对所有算法的影响相同。的影响相同。5*5的矩阵相乘与的矩阵相乘与10*10矩阵的矩阵相乘所需时间矩阵的矩阵相乘所需时间空间均不相同空间均不相同;找找c在数组在数组A中的位置中的位置,c=A(1),与与c=A(100),所需时间所需时间显然也显然也不同不同 顺序查找还是折半查找速度也是不一样的顺序查找还是折半查找速度也是不一样的.算法设计与分析算法设计与分析 算法概述算法概述22令令 n:n:问题规模问题规模 I:I:输入数据
16、输入数据 A:A:算法本身算法本身 C:C:算法的复算法的复杂性杂性,则则 C=f(n,I,A)C=f(n,I,A)将时间复杂性和空间复杂性分别考虑将时间复杂性和空间复杂性分别考虑,并用并用T T和和S S表示表示.则有则有:T=T(n,I,A)S=S(n,I,A)T=T(n,I,A)S=S(n,I,A)将算法将算法A A 隐含在函数名中隐含在函数名中,不同函数名代表不同算法不同函数名代表不同算法,则简化为则简化为 T=T(n,I)S=S(n,I)T=T(n,I)S=S(n,I)算法设计与分析算法设计与分析 算法概述算法概述23k1I)(n,etiii设一台抽象计算机提供的元运算有设一台抽象计
17、算机提供的元运算有k种种,记作记作 O1,Ok;设这些元运算每执行一次所需时间分别为设这些元运算每执行一次所需时间分别为 t1,tk;设在算法设在算法A中用到中用到Oi的次数为的次数为 ei,i=1,k,则则 ei=ei (n,I)T=T(n,I)=T=T(n,I)=当问题的规模当问题的规模 n和算法确定后和算法确定后,T是输入变元是输入变元 i 的函数的函数.仅以时间复杂性为例将复杂性函数具体化仅以时间复杂性为例将复杂性函数具体化.算法复杂性分析算法复杂性分析 复杂性的计量复杂性的计量 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述24说明:说明:我们不可能对规模为我们不可能
18、对规模为n的每一种合法输的每一种合法输入入I都计算都计算ei次,次,因为输入可能是无穷集合因为输入可能是无穷集合,我们只能对规模为我们只能对规模为n的问题的的问题的某类具有代表某类具有代表性性的合法输入统计相应的的合法输入统计相应的ei.算法复杂性分析算法复杂性分析 复杂性的计量复杂性的计量 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述25最好情况最好情况:T Tminmin(n)=T(n,I)=(n)=T(n,I)=kiiiInet1,)(kiiiInet1,)(kiiiInet1,)()(InT,kiiiInet1,)(nDImaxkiiiInet1*,)(NDIIPI)
展开阅读全文