- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法设计与分析论文
题 目0-1背包问题的算法设计策略对比与分析
专 业
班 级
学 号
姓 名
引言
对于计算机科学来说,算法(Algorithm)的概念是至关重要的。算法是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与 HYPERLINK /view/104946.htm \t _blank 时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。
一个算法应该具有以下五个重要的特征:
有穷性:一个算法必须保证执行有限步之后结束;
确切性:算法的每一步骤必须有确切的定义;
输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;
输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。
HYPERLINK /view/92404.htm \t _blank 计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》,可见算法在计算机科学界与计算机应用界的地位。
1 算法复杂性分析的方法介绍
算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的资源越低,则该算法的复杂性越低。
计算机的资源,最重要的是时间和空间(即存储器)资源。因而???算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻,对于任意给定的问题,设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标;另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是我们在选用算法适应遵循的一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
关于算法的复杂性,有两个问题要弄清楚:用怎样的一个量来表达一个算法的复杂性;对于给定的一个算法,怎样具体计算它的复杂性。
让我们从比较两对具体算法的效率开始。
1.1比较两对算法的效率
考虑问题1:已知不重复且已经按从小到大排好的m个整数的数组A[1..m](为简单起见。还设m=2 k,k是一个确定的非负整数)。对于给定的整数c,要求寻找一个下标i,使得A[i]=c;若找不到,则返回一个0。
问题1的一个简单的算法是:从头到尾扫描数组A。照此,或者扫到A的第i个分量,经检测满足A[i]=c;或者扫到A的最后一个分量,经检测仍不满足A[i]=c。我们用一个函数Search来表达这个算法:
Function Search (c:integer):integer;
Var J:integer;
Begin
J:=1; {初始化}
{在还没有到达A的最后一个分量且等于c的分量还没有找到时,
查找下一个分量并且进行检测}
While (A[i]c)and(jm) do
???????? j:=j+1;
If A[j]=c then search:=j {在数组A中找到等于c的分量,且此分量的下标为j}
else Search:=0; {在数组中找不到等于c的分量}
End;
容易看出,在最坏的情况下,这个算法要检测A的所有m个分量才能判断在A中找不到等于c的分量。
解决问题1的另一个算法利用到已知条件中A已排好序的性质。它首先拿A的中间分量A[m/2]与c比较,如果A[m/2]=c则解已找到。如果A[m/2]c,则c只可能在A[1],A[2],..,A[m/2-1]之中,因而下一步只要在A[1], A[2], .. ,A[m/2-1]中继续查找;如果A[m/2]c,则c只可能在A[m/2+1],A[m/2+2],..,A[m]之中,因而下一步只要在A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形,都把下一步需要继续查找的范围缩小了
您可能关注的文档
- 第四章分子对称性讲述.ppt
- 第四章其它微生物-1原核微生物讲述.ppt
- 第四章制造企业主要经济业务的核算讲述.ppt
- 装配电工技能培训详解.ppt
- 第四章动能和势能讲述.ppt
- 第四章分子生物学研究方法讲述.ppt
- 第四章化学平衡(物理化学-印永嘉)讲述.ppt
- 第四章励磁系统564-643讲述.doc
- 纳智捷活动总结(对内)151031详解.pptx
- 第四章刺胞动物门之一讲述.ppt
- 《GB/Z 44363-2024致热性 医疗器械热原试验的原理和方法》.pdf
- GB/T 16716.6-2024包装与环境 第6部分:有机循环.pdf
- 中国国家标准 GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 《GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统》.pdf
- GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 中国国家标准 GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 44305.2-2024塑料 增塑聚氯乙烯(PVC-P)模塑和挤塑材料 第2部分:试样制备和性能测定.pdf
- 《GB/T 44315-2024科技馆展品设计通用要求》.pdf
- GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 39560.9-2024电子电气产品中某些物质的测定 第9 部分:气相色谱-质谱法(GC-MS)测定聚合物中的六溴环十二烷.pdf
最近下载
- 理财教材《小狗钱钱》.pdf
- 护理品管圈问题解决型之提高慢性肾功能不全患者饮食指导知晓率.pptx VIP
- 复旦投毒案林森浩(详细的参考资料整理).docx
- Axure RP原型设计图解微课视频教程(Web+App)(刘刚)PPT全套完整教学课件.pptx
- 2024年国家电网招聘之财务会计类题库附参考答案(轻巧夺冠).docx
- 1精益管理倡导者培训.pptx
- 整本书阅读 《朝花夕拾》(同步课件) 七年级语文上册(统编版2024).pptx
- 2024-2029年中国房地产投资行业发展分析及投资风险预警与发展策略研究报告.docx
- 文旅融合背景下的文化遗产活化措施.pptx VIP
- 非物质文化遗产活化策略PPT.pptx VIP
文档评论(0)