算法引论及简单算法.pptx
《算法引论及简单算法.pptx》由会员分享,可在线阅读,更多相关《算法引论及简单算法.pptx(37页珍藏版)》请在咨信网上搜索。
1、补充材料补充材料1 算法引论及简单算法算法引论及简单算法清华大学 自动化系刘连臣2010年11月1日计算机语言与程序设计基础计算机语言与程序设计基础 1注注 意意2与数据结构的区别:与数据结构的区别:考虑问题的考虑问题的角度角度:数据结构关心不同的数据结构在解题中的作用和效率;算法关:数据结构关心不同的数据结构在解题中的作用和效率;算法关心不同设计技术的适用性和效率。心不同设计技术的适用性和效率。考虑问题的考虑问题的高度高度:数据结构关心的是解具体问题,算法不仅如此,它提供一种解:数据结构关心的是解具体问题,算法不仅如此,它提供一种解决问题的通用方法。决问题的通用方法。与其他课程的关系与其他课
2、程的关系高级程序设计语言(高级程序设计语言(C语言,等)语言,等)数据结构数据结构 算法设计算法设计与与分析分析 系统的设计与实现系统的设计与实现 3主要内容主要内容o目标:目标:了解算法分析的了解算法分析的了解算法分析的了解算法分析的基本含义基本含义基本含义基本含义。掌握。掌握。掌握。掌握查找算法查找算法查找算法查找算法、排序算法排序算法排序算法排序算法、递推算法递推算法递推算法递推算法等算法理念。等算法理念。等算法理念。等算法理念。提纲提纲补补1.1 1.1 算法分析算法分析补补1.2 1.2 查找算法查找算法补补1.3 1.3 排序算法排序算法补补1.4 1.4 递推算法递推算法4补补1
3、.1 算法分析算法分析o前面的课程内容以前面的课程内容以C语言语法为主语言语法为主o本补充章介绍一些基本算法本补充章介绍一些基本算法o大家在编写程序的时候,大家在编写程序的时候,“八仙过海,八仙过海,各显神通各显神通”,解决同一个问题,可以使,解决同一个问题,可以使用各种方法。用各种方法。o算法之间存在着算法之间存在着“优劣优劣”之分之分5补补1.1 算法分析算法分析1、算法分析的目的算法分析的目的 o通过对算法分析,在把算法变成程序实际运通过对算法分析,在把算法变成程序实际运行前,就知道为完成一项任务所设计的算法行前,就知道为完成一项任务所设计的算法的好坏,从而运行好算法,改进差算法,避的好
4、坏,从而运行好算法,改进差算法,避免无益的人力和物力浪费。免无益的人力和物力浪费。6补补1.1 算法分析算法分析2、算法分析的含义算法分析的含义o算法分析是一种分析技术,它以独立于具体的硬件平算法分析是一种分析技术,它以独立于具体的硬件平台、编译器和编程语言的方式,来描述算法的执行行台、编译器和编程语言的方式,来描述算法的执行行为,即它关心的是算法,而不是程序。为,即它关心的是算法,而不是程序。o算法分析是一种测量算法的性能的方法,它不关心精算法分析是一种测量算法的性能的方法,它不关心精确的细节,如在算法的某次运行中总共执行了多少条确的细节,如在算法的某次运行中总共执行了多少条机器指令,而是想
5、要一个大致的估计,即随着输入数机器指令,而是想要一个大致的估计,即随着输入数据规模的增大,算法所需工作量以何种速度递增。据规模的增大,算法所需工作量以何种速度递增。(关心变化趋势)(关心变化趋势)7补补1.1 算法分析算法分析3、算法复杂性算法复杂性 时间复杂性和空间复杂性时间复杂性和空间复杂性8补补1.1 算法分析算法分析1.有些计算机需要用户提供程序运行有些计算机需要用户提供程序运行时间的上限,一旦达到这个上限,时间的上限,一旦达到这个上限,程序将被强制结束。程序将被强制结束。2.正在开发的程序可能需要提供一个正在开发的程序可能需要提供一个满意的实时响应。满意的实时响应。为什么要考虑时间复
6、杂性?为什么要考虑时间复杂性?91.1.多用户系统中运行时,需指明分配给该程序的内多用户系统中运行时,需指明分配给该程序的内存大小。存大小。2.2.可提前知道是否有足够可用的内存来运行该程序。可提前知道是否有足够可用的内存来运行该程序。3.3.一个问题可能有若干个内存需求各不相同的解决一个问题可能有若干个内存需求各不相同的解决方案,从中择取。方案,从中择取。4.4.利用空间复杂性来估算一个程序所能解决问题的利用空间复杂性来估算一个程序所能解决问题的最大规模。最大规模。考虑程序的空间复杂性的理由:考虑程序的空间复杂性的理由:补补1.1 算法分析算法分析104.如何进行算法分析?如何进行算法分析?
7、o事前分析事前分析:就算法本身,通过对其执行性能的理论分析,:就算法本身,通过对其执行性能的理论分析,得出关于算法特性得出关于算法特性时间和空间时间和空间的一个特征函数的一个特征函数()与计算机软硬件没有直接关系。与计算机软硬件没有直接关系。o事后测试事后测试:将算法编制成程序后放到计算机上运行,收:将算法编制成程序后放到计算机上运行,收集其执行时间和空间占用等统计资料,进行分析判断集其执行时间和空间占用等统计资料,进行分析判断直接与物理实现有关。直接与物理实现有关。补补1.1 算法分析算法分析111)事前分析)事前分析o目的:试图得出关于算法执行特性的一种形式描目的:试图得出关于算法执行特性
8、的一种形式描 述,以述,以“理论上理论上”衡量算法衡量算法“好坏好坏”。o如何给出反映算法执行特性的描述如何给出反映算法执行特性的描述?最直接方法:最直接方法:统计算法中各种运算的执行情况:统计算法中各种运算的执行情况:运用了哪些运算运用了哪些运算 每种运算被执行的次数每种运算被执行的次数 该种运算执行一次所花费的时间该种运算执行一次所花费的时间 算法的执行时间算法的执行时间=Fi*ti补补1.1 算法分析算法分析12估算执行时间的方法估算执行时间的方法 选择一种或多种(如加、乘和比较等),然后确定这种(些)选择一种或多种(如加、乘和比较等),然后确定这种(些)操作分别执行了多少次。操作分别执
9、行了多少次。令令n代表程序实例特征,则执行时间计算公式为:代表程序实例特征,则执行时间计算公式为:TP(n)=c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+c1、c2、c3、c4分别表示一次加、分别表示一次加、减、乘、减、乘、除操作所需的时间。除操作所需的时间。函数函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表示程分别表示程序序P中,所使用的加、减、乘、中,所使用的加、减、乘、除操作的次数。除操作的次数。这种方法是否成功取决这种方法是否成功取决于识别关键操作的能力,于识别关键操作的能力,这些关键操作对时间复这些关键操作对时间复杂性的影响最大。杂性的影
10、响最大。一条语句在整个程序运行时实际执行时间一条语句在整个程序运行时实际执行时间=频率计数频率计数*每执行一次该语句所需的时间每执行一次该语句所需的时间补补1.1 算法分析算法分析13o频率计数:频率计数:算法中算法中语句语句或或运算运算的执行次数。的执行次数。例:例:x=x+y for(i=1;i=n;i+)for(i=1;i=n;i+)x=x+y;for(j=1;j=n;j+)x=x+y;(a)(b)(c)分析:分析:(a):x=x+y执行了执行了1次次 (b):x=x+y执行了执行了n次次 (c):x=x+y执行了执行了n2次次 注:在事前分析中,只限于确定与所使用机器及其他环境因素无关
11、的频率计注:在事前分析中,只限于确定与所使用机器及其他环境因素无关的频率计数,依此建立一种理论上分析模型。数,依此建立一种理论上分析模型。补补1.1 算法分析算法分析14o数量级数量级语句的数量级语句的数量级:语句的执行频率。:语句的执行频率。例:例:1,n,n2 算法的数量级算法的数量级:算法包含所有语句的执行频率之和。:算法包含所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。例:求解同一问题的三个算法分别具有例:求解同一问题的三个算法分别具有n,n2,n3数量级。数量级。若若n=10,则可能的执行时间将分别是,则可能的执行
12、时间将分别是10,100,1000 个单位时间个单位时间与环境因素无关。与环境因素无关。补补1.1 算法分析算法分析15补补1.1 算法分析算法分析5、算法复杂性的等级算法复杂性的等级o常量阶常量阶n时间复杂度为时间复杂度为O(1)n算法运行时间不随着问题的规模而变化算法运行时间不随着问题的规模而变化n如:如:o简单的赋值语句,简单的赋值语句,x=y;o算术运算,算术运算,x=y*5+z%3;o固定次数的循环语句等固定次数的循环语句等for(i=0;i10;i+)for(j=0;j20;j+)aij=0;16补补1.1 算法分析算法分析o线性阶线性阶n时间复杂度为时间复杂度为O(n)n算法运行
13、时间随着问题的规模而成线性变化算法运行时间随着问题的规模而成线性变化for(i=0;in;i+)sum=sun+i;算法执行了多少次运算?算法执行了多少次运算?i=0;执行了执行了1次次in;执行了执行了n+1次次i+;执行了执行了n次次sum=sun+i;执行了执行了n次次共执行了共执行了3n+2次运算次运算时间复杂度就是时间复杂度就是O(3n+2)实际上,算法的时间复杂度并不精确实际上,算法的时间复杂度并不精确计算基本操作的执行次数,它主要考计算基本操作的执行次数,它主要考虑问题规模的增长率。虑问题规模的增长率。O(n)17补补1.1 算法分析算法分析o平方阶平方阶n时间复杂度为时间复杂度
14、为O(n2)n算法运行时间随着问题的规模而成平方变化算法运行时间随着问题的规模而成平方变化for(i=0;in;i+)for(j=0;jn;j+)sum=sun+aij;/执行执行n2次次printf(“%dn”,sum);/执行执行n次次时间复杂度就是时间复杂度就是O(n2)18补补1.1 算法分析算法分析o多项式阶多项式阶n时间复杂度为时间复杂度为O(nd)d为固定常数为固定常数n算法运行时间随着问题的规模而成算法运行时间随着问题的规模而成d次多项式阶变化次多项式阶变化o对数阶对数阶 O(logn)o指数阶指数阶 O(log2n)o阶乘阶阶乘阶 O(n!)o若若T(n)=adnd+a1n+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 引论 简单
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。