算法设计与分析 第一二章 引言 复杂性分析初步

《算法设计与分析 第一二章 引言 复杂性分析初步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章引言凡是学习了一种语言（不论是初级的还是高级的）程序设计课程并能编写一些实用程序的人，也许都有这样一种体会，学会编程容易，但是要想编出好程序难，因而很想学点如何设计良好算法的知识。一些著名的计算机学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是面向设计、处于核心地位的课程。本课程本着理论联系实际、以实际问题为背景、学以致用的原则，向大家讲解计算机算法设计和性能分析的基本方法。虽然人们对算法（algorithm）一词非常熟悉，可到目前为止，对于算法尚没有

2、统一而精确的定义。有人说：算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算（《计算机算法基础》邹海明、余祥宣编）。而ThomasH.Cormen等人在“IntroductiontoAlgorithms”一书中将算法描述为：算法是任何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。因此，算法是将输入转化为输出的一系列计算步骤。我们也可以把算法看作解特定的计算问题的工具。概括起来，算法有以下五个特性：1．确定性：算法的每一种运算（包括判断）必须要有确切的定义，即每一种运算应该

3、执行何种动作必须是相当清楚的、无二义性的。2．可实现性：此性质是指算法中有待实现的运算都是相当基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。3．具有数据输入：一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量，这些输入取自特定的对象集合。4．具有数据输出：一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。5．有穷性：一个算法总是在执行了有穷步之后终止。程序是算法的计算机高级语言描述，算法更可看成是程序的灵魂。一般来说，拟定一个算法要经过设计、确认、分析、编码、检查、调试、计时等阶

4、段。据此，算法的学习大致可以分为五个方面：Ø如何设计算法Ø如何表示算法Ø如何确认算法Ø如何分析算法Ø如何测试算法教学大纲课程编号课程属性学科基础课学时/学分中文课程名称计算机算法设计与分析英文课程名称TheDesignandAnalysisofComputerAlgorithms预备知识离散数学、数据结构、高级程序设计语言C、C＋＋教学目的和要求计算机及相关学科硕士研究生的基础课。使学生掌握计算机算法的通用设计方法，学会分析算法的空间和时间复杂性。发展方向计算机算法设计和软件开发考核办法平时考察30％＋期末闭卷考试70％参

5、考资料1．余祥宣等，《计算机算法基础》，华中理工大学出版社，2000。2．（美）Cormen，T.H.等，《算法导论》，高等教育出版社，2001。3．王晓东，《计算机算法设计与分析》，电子工业出版社，2001。撰写人范书国撰写日期2006年2月18日第二章复杂性分析初步程序性能（programperformance）是指运行一个程序所需的内存大小和时间多少。所以，程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主要包含两方面，即性能分析（performanceanalysis）与性能测量（performancemea

6、surement），前者采用分析的方法，后者采用实验的方法。考虑空间复杂性的理由ü在多用户系统中运行时，需指明分配给该程序的内存大小；ü想预先知道计算机系统是否有足够的内存来运行该程序；ü一个问题可能有若干个不同的内存需求解决方案，从中择取；ü用空间复杂性来估计一个程序可能解决的问题的最大规模。考虑时间复杂性的理由ü某些计算机用户需要提供程序运行时间的上限（用户可接受的）；ü所开发的程序需要提供一个满意的实时反应。选取方案的规则：如果对于解决一个问题有多种可选的方案，那么方案的选取要基于这些方案之间的性能差异。对于各种方案

7、的时间及空间的复杂性，最好采取加权的方式进行评价。但是随着计算机技术的迅速发展，对空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强调时间复杂性的分析。§1空间复杂性程序所需要的空间：l指令空间－用来存储经过编译之后的程序指令。程序所需的指令空间的大小取决于如下因素：ü把程序编译成机器代码的编译器；ü编译时实际采用的编译器选项；ü目标计算机。所使用的编译器不同，则产生的机器代码的长度就会有差异；有些编译器带有选项，如优化模式、覆盖模式等等。所取的选项不同，产生机器代码也会不同。此外，目标计算机的配置也会影响代

8、码的规模。例如，如果计算机具有浮点处理硬件，那么，每个浮点操作可以转化为一条机器指令。否则，必须生成仿真的浮点计算代码，使整个机器代码加长。一般情况下，指令空间对于所解决的特定问题不够敏感。l数据空间－用来存储所有常量和变量的值。分成两部分：a).存储常量和简单变量；b).存储复合变量。前者所需的空间取