计算机算法设计与分析-read.ppt

计算机算法设计与分析 中南大学信息学院 郑 瑾 Zhengjin@mail.csu.edu.cn 教学目的和要求 本课程为计算机科学与技术学科本科生的学科基础课程。（注意：不是语言课，也不是数学课） 通过对常用的、有代表性的算法的研究，理解并掌握算法设计的基本技术。 学会对算法的时间和空间的复杂性进行分析，掌握提高算法效率的方法和途径。 能力培养要求 算法设计与分析是计算机科学的一个主要研究领域。通过本课程的学习，培养学生在选择或设计一个算法时，思考下列问题：这个算法是否有效？这个算法有多好？是否还有更好的算法？用什么方法和技巧去获得更好的算法？从而使得所设计的算法的时空复杂性最优，进而为编写高效的程序、开发优秀软件奠定基础。 ? 课程主要内容 绪论 分治法 贪心法 动态规划方法 回朔法 分枝-限界方法 教材和主要参考书 1．教材：余祥宣等，《计算机算法基础》，华中科技大学出版社，武汉，1998。定价：19.8元 2.Anany Levitin, Introduction to The Design Analysis of Algorithms (算法设计与分析基础（影印板） 清华大学出版社（定价39.00元) 第一章 绪论 1. 算法概述 对于计算机科学来说，算法（Algorithm）的概念是至关重要的。例如一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是由若干条指令组成的有穷符号串，且满足以下几条性质： 算法的五个重要特性 （1）输入：有零个或多外由外部提供的量作这算法的输入。 （2）输出：算法产生至少一个量作这输出。 （3）确定性：组成算法的每条指令是清晰的，无歧义的。 （4） 可实现性 ：算法中有待实现的运算都是相当基本的， 每种运算至少在原理上能由人用纸和笔在有限的时间内完成能行性 。 （5）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 如何设计算法 通过学习已被实践证明是有用的一些基本设计策略，掌握一般的算法设计方法，学会设计高效的算法。 如何表示（描述）算法 描述算法可以有多种方式，如自然语言方式、表格方式等。 本教案依循教材，并考虑到学生的特点选择了类C语言和类SPARKS的语言结合的伪代码来表示算法。只要学过高级语言的人，都很容易掌握这种描述。 如何确认算法 证明算法对所有可能的合法输入都能算出正确的答案，这一工作称为算法确认。这一领域是当前很多计算机科学工作者集中研究的对象，还处于相当初期的阶段。 在学习本课程中，我们仅对算法的正确性进行一般的非形式化的讨论和对算法的程序实现进行测试。 如何分析算法 分析算法包括定量地分析算法需要多少计算时间和存储空间。 分析算法不仅可以预计算法能否有效地完成任务，而且可以知道在最好、最坏和平均情况下运算时间，对解决同一问题不同算法的优劣做出比较。 1.1 算法的复杂性 算法的复杂性是是算法效率的度量，是评价算法优劣的重要依据。 一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上。所需资源越多，我们就说该算法复杂性高；反之，所需资源少，就说该算法的复杂性越低。 计算机的资源，最重要的是时间和空间(即存储器) 资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 本课程主要对算法的时间复杂性行分析。关于算法的复杂性，有两个问题要弄清楚： (1)用怎样的一个量来表达一个算法的复杂性。 (2)对于给定的一个算法，怎样具体计算它的复杂性。 算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。这个量应该集中反映算法的效率，并从运行该算法的实际计算机中抽象出来。也就是说，这个量应该是只依赖于要解的问题的规模、算法的输入和算法本身的函数。如果用N、I和A表示算法要解的问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F（N，I，A），其中F（N，I，A）是一个由N、I和A确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，则应有：T=T（N，I，A）和S=S（N，I，A） 但一般省略A,而写为:T=T（N，I）和S=S（N，I） 时间复杂性函数的具体化？ 即对于给定的N、I和A，如何导出T=T（N，I）和S=S（N，I）？ T（N，I）表示算法在一台抽象的计算机上运行需要的时间。设此抽象计算机的元运算有k种，分别记为O1，O2，