计算机算法基础(第2章)

《计算机算法基础(第2章)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、章节安排第2章导引与基本数据结构√第3章递归算法√第4章分治法√第5章贪心方法√第6章动态规划√第7章检索与周游√第8章回溯法√第9章分枝-限界√第10章NP-问题⊙第11章并行算法⊙算法问题举例问题描述在N件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。第2章导引与基本数据结构2.1算法的定义及特性1.什么是算法？算法如数字、计算一样，是一个基本概念。算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词：算法是一组有穷的

2、规则，它规定了解决某一特定类型问题的一系列运算。2.算法的五个重要特性确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算5/06+x未赋值变量参与运算2）能行性算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。例：整数的算术运算是“能行”的实数的算术运算是“不能行”的3）输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）4）输出一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5）有穷性一个算法总是

3、在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。准确理解算法和计算过程的区别：不能终止的计算过程：操作系统算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行算法和程序程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现任何程序设计语言都可以实现任何一个算法算法的有穷性意味着不是所有的计算机程序都是算法3.我们的主要任务算法学习将涉及5个方面的内容：1）设计算法：创造性的活动2）表示算法：思想的表示形式3）确认算法：证明算法的正确性程序的证明4）分析算法：算法时

4、空特性分析5）测试程序：“调试只能指出有错误，而不能指出它们不存在错误”本课程集中于学习算法的设计与实现。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础被实践证明是有用的基本设计策略算法所需时间和空间的定量分析4.课程关系数据结构、离散数学程序设计语言：结构化设计数学基础非数值计算领域的基本知识2.2分析算法计算机程序设计的核心目标：1、设计一个容易理解、编码和调试的算法2、设计一个能有效利用计算机资源的算法怎样度量效率？－－算法分析1.分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计

5、的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的古老而前沿的课题。进行算法分析的基本技术：抽象2.重要的假设和约定1）计算机模型的假设Turing机模型：计算机形式理论模型通用计算机模型：顺序计算机有足够的“内存”能在固定的时间内存取数据单元2）计算的约定算法的执行时间=∑Fi*ti其中，Fi是算法中用到的某种运算i的次数，ti是该运算执行一次所用的时间。确定使用什么样的运算及其执行时间。从计算时间上，运算的分类：时间囿界于常数的运算：·基本算术运算，如整数、浮点数的加、减、乘、除·字符运算·赋值运算·过程调用等特点：尽

6、管每种运算的执行时间不同，但一般只花一个固定量的时间（单位时间）就可完成。2）计算的约定（续）其他运算：·字符串操作：与字符串中字符的数量成正比·记录操作：与记录的属性数、属性类型等有关·特点：运算时间无定量如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。如：Tstring=Length（String）*tchar3）工作数据集的选择编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。测试数据集的生成在目前算法证明与程序正确性证明没有取得理论上的突破性进展的情况下，是程序测试与算法分析中的关键技术之

7、一。·作为算法分析的数据集：典型特征·作为程序性能测试的数据集：对执行指标产生影响的性质3.如何进行算法分析？对算法进行全面分析，可分两个阶段进行：事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο、Ω）——与计算机物理软硬件没有直接关系。事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。1）事前分析目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行