计算机算法设计与分析 五种常用算法.docx

浅论五个常用算法
软件工程
姓 名:余智昆
专业班级:软件102班
日 期:
【摘要】随着信息工业的发展,计算机已然成为人们日常生活中不可或缺的工具。目前,
各行业、各领域都广泛采用了计算机信息技术,并由此产生浅论五个常用算法
软件工程
姓 名:余智昆
专业班级:软件102班
日 期:
【摘要】随着信息工业的发展,计算机已然成为人们日常生活中不可或缺的工具。目前,
各行业、各领域都广泛采用了计算机信息技术,并由此产生出开发各种应用软件的需求。为了以最少的成本、最快的速度、最好的质量开发出适应各种应用需求的软件,必须遵循软件工程的原则。设计一个高效的程序不仅需要编程小技巧,更需要合理的数据组织和清晰高效的算法,这正是计算机科学领域数据结构与算法设计所研究的主要内容。通过对计算机算法系统的学习与研究,掌握算法设计的主要方法,培养对算法的计算复杂性正确分析的能力,为独立设计算法和对算法进行复杂性分析奠定了坚实的理论基础。
在计算机语言中,算法的概念是至关重要的,一个优秀的软件,设计出有效的算法将起决定性的作用。本篇论文将对五种常用算法概括总结,希望能够对算法有更深入的理解。
【关键词】递归与分治策略、动态规划、贪心算法、回溯法、分之界限法
【正文】
一、 递归与分治策略
:一个直接或间接调用自身的算法称为递归算法。在计算机算法设计与分析中,使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树等,由于其本身固有的递归特性,特别适合用递归形式来描述。还有一些问题,虽然本身并没有明显的递归结构,但是用递归技术来求解设计出的算法简洁易懂且易于分析。
递归算法要求:递归算法所体现的“重复”一般有三个要求
一是每次调用在规模上都有所缩小(通常是减半);
二是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);
结束
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。
开始 :
~rr一 递归算法的实现类似于多个
算法的嵌套调用,只是n调用算法和被调用算法是同一个算法。和每次调用相关的一个重要概念是递归算法的调用层次。若调用一个递归算法的主算法为第0层算法,则主算法调用递归算法为进入第一层调用;从第i层递归调用本算法为进入第i+1层调用。反之,退出第i否层调用,则返回第i-1」层递归调用。为了保证递归调用正确执行,系统要建立一个递归调用工作栈,为各层次的调用数据存储区。
:结构清晰、可读性强,且容易用数学归纳法证明算法的正确性,因此它为设计算法、调试程序带来很大的方便。然而,递归算法的运行效率较低,无论是耗费的计算时间还是占用的空间都要比非递归算法要多。因此,我们使用递归算法,必须权衡运行时间与内存这两者的消耗。
:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题
的解。这种算法设计