算法分析基础.ppt
《算法分析基础.ppt》由会员分享,可在线阅读,更多相关《算法分析基础.ppt(70页珍藏版)》请在咨信网上搜索。
1、第1章 算法分析基本概念 曹霑懋算法设计技巧与分析.Chapter 1 Basic Concepts in Algorithmic Analysis 内容1.1 Introduction l.2 Historical Background 1.3 Binary Search 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 1.5 Selectinn Sort 1.6 Insertion Sort 1.7 Bottom-Up Merge Sorting 1.7.1 Analysis of bot
2、tom-up merge sorting 2024/5/10 周五2.1.8 Time Complexity 1.8.1 Order of growth 1.8.2 The O-notation 1.8.3 The fl-notation l.8.4 The e-notation 1.8.5 MamPles 1.8.6 Complekity classes and the o-notation 1.9 Space Complexity 1.10 Optimal AlgorithmsChapter 1 Basic Concepts in Algorithmic Analysis 内容2024/5
3、/10 周五3.1.1 引言 Donald E.Knuth:计算机科学就是算法的研究.每个领域:依赖 有效算法设计运行时间:由例子到理论时间是衡量算法有效性的最好测度算法的几个方面:输入有限指令集输出 (存在?Y/N)2024/5/10 周五4.算法概念算法是程序设计的精髓,程序设计的实质就是细化构造解决问题的算法,将其解释为计算机语言。算法算法是在有限有限步骤内求解某一问题所使用的一组定义明确的指令(规则)。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。一个算法应该具有以下五个重要的特征:有穷性:
4、有穷性:一个算法必须保证执行有限步之后结束;确切性:确切性:算法的每一步骤必须有确切的定义;输入:输入:一个算法有0个或多个输入,以刻画运算对象的初始情况;输出:输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;可行性:可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。2024/5/10 周五5.算法 几点说明 1.“算法”的 2.“算法”的现代诠释 3.学习“算法”的方法 几个词:Algorithm、Logarithm、Algorism 算法的现代意义十分类似于处方、过程、方法、规程、程序,一个算法就是有穷规则的集合一个算法就是
5、有穷规则的集合。其中,规则规则规定了一个解决某一特定类型的问题的运算序列。一个算法应该是可以信赖的,而且学习一个算法直到彻底掌握的最好方法是反复进行试验。因此,遇到一个算法时,应该找出这个算法的一个例子,给出该例子的要点进行试验。2024/5/10 周五6.程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性的性质。例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。程序(Program)2024/5/10 周五7.1.2 历史背景 20世纪,早期
6、,30年代 能否用有效的过程来求解问题受到关注问题分类为:可解、不可解(存在有效过程来求解问题)计算模型:存在模型,用此模型能建立一求解某问题的算法,入可解的类模型列举:歌德尔的递归函数,Church的Lamda演算,Post的波斯特机,Turing机。Church论断:所有4个模型等效。如果一个问题在某一模型上可解,那么在其他模型上都是可解的。“几乎所有”问题都是不可解的。确定一个包含N个变量的多项式方程是否有整数解简单理由陈述:P3Top可判定性可计算性理论,可解性计算理论;有Digital Computer后,对可解问题的研究的要求越来越多。程序,资源量,尽可能少使用资源(时间,空间)的
7、有效算法的需求。效率:指解决问题所需时间和空间排序一组元素的算法作为研究的实例表明:设计了许多有效算法,解决问题的效率将不会因其他方法而有大的提高。2024/5/10 周五8.好的算法所具备的意义2024/5/10 周五9.衡量算法性能的标准衡量算法性能一般有下面几个标准衡量算法性能一般有下面几个标准正确性易读性健壮性算法的时间和空间性能:高效率和低存储空间 我们这里主要讨论算法的时间和空间性能,并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。2024/5/10 周五10.算法的表达机制【表达算法的抽象机制表达算法的抽象机制】对于一个明确的数学问题,设计它的算法,总是先选用该问题
8、的一个数学模型。接着,弄清该问题数学模型在已知条件下的初始状态和要求的结果状态,以及这两个状态之间的隐含关系。然后探索从数据模型的已知初始状态到达要求的结果状态所需的运算步骤。2024/5/10 周五11.算法的描述方法算法的描述方法自然语言;图表;框图;计算机语言或程序设计语言等。如,汇编、C+、Java。2024/5/10 周五12.1.3 二分搜索二分搜索假定元素满足:线序集合1n 中有吗?从头到尾的扫描,比较次:顺序搜索顺序搜索适合无序的集合有序的集合:BinarySearch要求能够写出:这个简单的算法,并分析运算量。2024/5/10 周五13.1.3-(例)线性查找的时间评估最小
9、查找时间?最小查找时间?最好情况最好情况,A1=X,A1=X平均查找时间?平均查找时间?P(i)=1/n,TP(i)=1/n,Tavgavg(n)=n/2(n)=n/2最大查找时间?最坏情况最大查找时间?最坏情况,x,x 不在不在A1.nA1.n或或x=An,x=An,复杂度为复杂度为n n2024/5/10 周五14.1.3 二分搜索及其时间复杂度 线性搜索二分搜索 同数据结构,略。但要求作为例子或问题求解。同数据结构,略。但要求作为例子或问题求解。及其算法分析及其算法分析2024/5/10 周五15.比较次数分析中,次循环时剩余元素数目Floor(n/2j-1)循环停止条件:找到,或当前查
10、找范围的数组长度为。最大搜索次数:满足Floor(n/2j-1)=1 时的值即:n/2j-1 2也即:2j-1n 2jj-1 log n j j=Floor(log n)+12024/5/10 周五16.随堂练习设有序数组:试搜索x=20,以及 X=22.1)拟用什么法?为什么?2)试给出用你想要得算法求解的过程。参考:教材binarySearch Example 1.12024/5/10 周五17.二分查找的基本运算量分析?2024/5/10 周五18.1.10 最优算法定义:排序问题中的2024/5/10 周五19.1.11-14.算法分析(Algorithm Analysis)算算法法分
11、分析析:对于算法的时间和空间复杂度进行定量分析。分析算法时间复杂度的基本步骤元运算考察可以做基本运算的有那些,选基本运算基本运算的总量评估借助数学公式,比如循环嵌套就是乘法原理,递归调用对应递归公式等求解2024/5/10 周五20.简例估计算法运行时间算法时间复杂度的有关概念:,平均分析、求解算法复杂度的基本方法设计计算过程如下:(为讨论方便,每行前加一行号)(1)for i:=1 to n(2)for j:=1 to n(3)x:=x+1.试问在程序运行中各步执行的次数各为多少?上例中的赋值操作基本运算时间复杂性可粗略地表示为f(n)=O(n2)。要更多地了解关于算法的复杂性,就必须弄清楚
12、如下两个问题:(1)用怎样的一个量来表达一个算法的复杂性;(2)对于给定的一个算法,怎样具体计算它的复杂性。2024/5/10 周五21.分析时间复杂度的基本步骤分析时间复杂度的基本步骤一、选取一种选取一种元运算元运算作为作为基本运算基本运算二、表示出在算法运行期间二、表示出在算法运行期间基本运算基本运算执行的总频数执行的总频数三、渐近时间复杂度(三、渐近时间复杂度(asymptotic time complexity)2024/5/10 周五22.思考与练习思考与练习:指出下面程序段中语句标*的频度和该程序段的时间复杂性。(1)*y:=sin(x);(2)for i:=1 to n-1 do
13、 *y:=y+1;for j:=0 to 2*n do *x:=x+1;(3)x:=1;y:=1;for k:=1 to n do *x:=x+1;for i:=1 to n do for j:=1 to n do *y:=y+1;(4)i:=1;while(i0和一个自然数n0,使得 对于n n0,均 f(n)cg(n),则称 f(n)=O(g(n)。(充分性)如果 f(n)/g(n)关于极限存在,那么就有f(n)=O(g(n)。2024/5/10 周五28.8.3.8.3渐近表示的记号渐近表示的记号 -记号记号 设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c0和一个
- 配套讲稿:
如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。