辛运帏全套配套课件数据结构与算法 DSChapter02.ppt

《辛运帏全套配套课件数据结构与算法 DSChapter02.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章算法的基本概念与算法分析2.1算法的基本概念2.2算法的评估2.3算法的复杂性度量2.1.1一个简单的算法问题把摄氏温度值转换为华氏温度值。已知计算公式为：F=(9/5)C+32，其计算过程可描述如下：输入一个摄氏温度值C；C乘以常数9/5=1.8；乘积与常数32相加；输出相加的结果F。这就是求解该问题的算法，不过，计算机“看”不懂这个算法，需要用程序设计语言描述：#include＜iostream.h＞voidmain（）{floatC,F；constfloatfac=1.8，inc=32.0；cout<<"EnterCelsiustemperature："；cin>

2、>C；∥输入摄氏温度值F=C；F=Cfac；F=F+inc;cout<

3、Knuth定义：一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列；此外，它还应有五个重要特性：有穷性：一个算法必须总是在执行有穷步之后结束；确定性：算法的每一步骤，必须是确切地定义的；输入：有0或多个输入值；输出：有1或多个输出值；能行性：算法中要做的运算都是相当基本的，能够精确地进行的。3.形式化定义：算法就是一个对任一有效输入能够停机的Turing机。2.1.3算法与问题如同生物学家把自然界的所有生物作为自己的研究对象，计算（Computation）学科或称计算机科学则把问题作为自己的研究对象。用计算机来解决问题（Problemsolv

4、ing）称为问题求解。算法要解决的是一类问题，算法的执行则针对的是问题的实例。每一个问题都可以看作是该问题的所有实例（instance）的集合。一个问题的一个实例就是为计算该问题所需的一组输入。例：整数乘法问题全部可能输入集合：{

5、a,b∈Z}，其中Z表示整数集；一个实例：<2,4>,求：2×4=?旅行商问题(TravelingSalesmanProblem)实例集为：{n,Wn*n=[Wij]

6、n∈Z,Wij∈R,i,j∈[1,…,n]}；一个实例：n=4,该实例（n,W）就是求环游4个城市(1,2,3,4)且代价和最小的周游路线，其中权矩阵W给出了4个城市之间的距

7、离（代价），Wij表示由城市i到城市j的距离（代价）。语言L的识别问题其中G为文法，Σ为一字符集。L(G)为Σ上由G生成的语言，L(G)∈Σ*，Σ*表示由Σ中的字符组成的所有字符串集合。语言L的识别问题{G,Σ,ω

8、ω∈Σ*}的一个实例ω∈Σ*，识别算法判断ω∈L(G)是否成立。一般对于问题P，总有其相应的实例集I，那么，一个算法A是问题P的算法，意味着把P的任一实例input∈I作为A的输入，都能得到问题P的正确的输出。一个问题可以有许多个不同的算法。2.1.4算法与程序程序(Program)可以用来描述算法，同一个算法可以用不同的语言编写的程序来描述。程序不一定是

9、算法。程序设计可以分为四个层次：算法、方法学、语言和工具。抽象级更新速度算法程序设计方法程序设计语言编程工具2.2.1算法的正确性算法的正确性是评估的前提。有些算法，特别是一些十分精致巧妙的算法，其正确性需要证明，有的证明难度较大，例如无向图单源最短路径问题的Dijkstra算法，构造最优二分搜索树的动态规划算法的Knuth改进。有些算法，其正确性是明显的，例如选择排序算法。2.2.2时间代价评估算法的时间代价是算法分析的核心。算法的时间代价的大小用算法的时间复杂度(TimeComplexity)来度量。但要考虑到以下因素：用来运行算法的计算机的性能的差别；算法运行的软件平台和

10、描述语言的差别；算法所解的问题是多种多样的；同一问题的算法对不同的实例，所花的时间开销也可能有很大的差别。2.2.3空间代价空间消耗是衡量算法优劣的另一重要因素。算法的空间代价的大小用算法的空间复杂度（SpaceComplexity）来度量。不过算法的空间复杂性分析的重要性常常列于时间复杂性分析之后。在许多应用问题中，人们往往以适当增加算法的空间代价来减少时间代价。空间复杂度的分析类似于时间复杂度的分析，其有关的概念和方法几乎是平行的。2.2.4最优性一个算法不一定是最优的。所谓最优算法是指