算法分析与设计论文-背包问题的算法设计策略对比与分析.doc
《算法分析与设计论文-背包问题的算法设计策略对比与分析.doc》由会员分享,可在线阅读,更多相关《算法分析与设计论文-背包问题的算法设计策略对比与分析.doc(16页珍藏版)》请在咨信网上搜索。
1、算法设计与分析论文题 目0-1背包问题的算法设计策略对比与分析专 业 班 级 学 号 姓 名 引言对于计算机科学来说,算法(Algorithm)的概念是至关重要的。算法是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。算法可以使用自然
2、语言、伪代码、流程图等多种不同的方法来描述。一个算法应该具有以下五个重要的特征:有穷性:一个算法必须保证执行有限步之后结束;确切性:算法的每一步骤必须有确切的定义; 输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件; 输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法= 程序,可见算法在计算机科学界与计算机应用界的地位。1 算法复杂性分析的方法介绍算法的复杂性是算法效率的度量
3、,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的资源越低,则该算法的复杂性越低。 计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻,对于任意给定的问题,设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标;另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是我们在选用算法适应遵循的一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性,有两个问题要弄清楚:用怎样的
4、一个量来表达一个算法的复杂性;对于给定的一个算法,怎样具体计算它的复杂性。让我们从比较两对具体算法的效率开始。1.1比较两对算法的效率考虑问题1:已知不重复且已经按从小到大排好的m个整数的数组A1.m(为简单起见。还设m=2 k,k是一个确定的非负整数)。对于给定的整数c,要求寻找一个下标i,使得Ai=c;若找不到,则返回一个0。问题1的一个简单的算法是:从头到尾扫描数组A。照此,或者扫到A的第i个分量,经检测满足Ai=c;或者扫到A的最后一个分量,经检测仍不满足Ai=c。我们用一个函数Search来表达这个算法:Function Search (c:integer):integer;Var
5、J:integer; BeginJ:=1; 初始化在还没有到达A的最后一个分量且等于c的分量还没有找到时,查找下一个分量并且进行检测 While (Aic)and(jc,则c只可能在A1,A2,.,Am/2-1之中,因而下一步只要在A1, A2, . ,Am/2-1中继续查找;如果Am/2=L时,继续查找While (not Found) and (U=L) doBeginI:=(U+L) div 2;找数组的中间分量If c=AI then Found:=Tureelse if cAI then L:=I+1 else U:=I-1;End;If Found then B_Search:=1
6、else B_Search:=0;End;容易理解,在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底,下同)个分量,就判断c是否在A中。算法Search和B_Search解决的是同一个问题,但在最坏的情况下(所给定的c不在A中),两个算法所需要检测的分量个数却大不相同,前者要m=2 k个,后者只要k+1个。可见算法B_Search比算法Search高效得多。以上例子说明:解同一个问题,算法不同,则计算的工作量也不同,所需的计算时间随之不同,即复杂性不同。上图是运行这两种算法的时间曲线。该图表明,当m适当大(mm0)时,算法B_Search比算法Search省时,而且当m
7、更大时,节省的时间急剧增加。不过,应该指出:用实例的运行时间来度量算法的时间复杂性并不合适,因为这个实例时间与运行该算法的实际计算机性能有关。换句话说,这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率,而不想去比较运行该算法的计算机的性能。因而,不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望,尽量单纯地反映作为算法精髓的计算方法本身的效率,而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。1.2复杂性的计量算法的复杂性是算法运行所需要的计算机资源的量,需要的时间资源的量称作时间复
8、杂性,需要的空间(即存储器)资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率,而从运行该算法的实际计算机中抽象出来。换句话说,这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身,用C表示算法的复杂性,那么应该有:C =F(N,I,A)其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开,并分别用T和S来表示,那么应该有:T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常,我们让A隐含在复杂性函数名当中,因而将(2.1)和(2.2)分
- 配套讲稿:
如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。