§6.3 算法

1.算法的基本概念

算法是计算机学科中的核心概念。算法的优劣决定着程序以至软件系统的性能。任何问题的解决都必需设法用数学方法来描述或模拟这些实际问题。把对实际问题的可行性解决方案归纳为计算机能够执行的若干步骤，再把这些步骤用一组计算机指令进行描述，形成所谓的计算机程序，最后交给计算机执行。算法：是指解题方案的准确而完整的描述, 是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制。算法是问题解决的程序化方案，其发现过程与一般问题求解过程之间存在着紧密的联系。 

（1）传统意义上对算法的理解：

算法是指对解题方案准确而完整的描述。可以将算法理解为对问题解决步骤的描述。如果这个问题用计算机来实现，则可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果。

计算机系统中的任何软件，都各自按照特定的算法来实现，算法的好坏直接决定软件性能的优劣。因此，算法设计与分析是计算机科学与技术的一个核心问题。

（2）算法胜利, 自由意志将终结

人类千百年来一直在追求自由意志，但是计算机算法的强大，很可能会让人丢掉“听从自己内心”的自由，转而把更多事情交由机器决定。最终，人们可能会授权算法来替他们做生命中最重要的决定。

（3）算法的特征

⑴可行性   算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

⑵确定性   是指算法中每一个步骤都必须有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

⑶有穷性  是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法的有穷性还应包括合理的执行时间的含义，如果一个算法需要执行数年甚至更久，显然就失去了实用价值。

⑷输入  通常，算法中的各个运算总是要施加到各个运算对象上，而这些对象又可能具有某种初始状态，这是算法执行的起点或依据。因此，算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出，也可以没有输入。当输入不够或输入错误时，算法本身也无法执行或执行出错。

⑸输出    一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法毫无意义。

2. 算法的表示

算法是对解题过程的精确描述，这种描述是建立在语言基础之上的。表示算法的语言主要有自然语言、程序流程图、伪代码、计算机程序设计语言等。

自然语言

自然语言是指人们日常所用的语言，如汉语、英语、德语等。自然语言存在着歧义性容易使算法在描述时具有不确定性；对于较为复杂的算法，很难清晰地表示出来；用自然语言表示的算法不方便于翻译成计算机程序设计语言的程序。

程序流程图

程序流程图是描述算法的常用工具，可以很方便地表示程序的基本控制结构。用流程图表示的算法不依赖于任何具体计算机程序设计语言，从而有利于不同环境的程序设计。

如下一组图形符号常用来表示算法：

求1+2+3+。。。+100的算法流程图

伪代码

伪代码是用介于自然语言和计算机语言之间的文字和符号的描述算法的工具

【例】输入3个数，打印输出其中最大的数。

伪代码表示：

Begin（算法开始）

输入 A，B，C

IF A>B  则 A→Max

否则 B→Max

IF C>Max  则 C→Max

Print Max

End （算法结束）

计算机程序设计语言

计算机不能识别自然语言、流程图和伪代码等算法描述语言，而设计算法的目的就是要用计算机解决问题。因此用自然语言、流程图和伪代码等语言描述的算法最终还必须要转换为具体的计算机程序设计语言编写的程序。计算机程序是基于某种计算机语言对算法的具体实现。可以用不同的计算机语言编写程序实现同一个算法，算法只有转换成计算机程序才能在计算机上运行。

3、算法的评价

1、正确性

算法的执行结果应该满足预先规定的功能和性能要求。对于各组典型的带有苛刻条件的输入数据也应得出正确的结果。

2、可读性

一个算法应该思路清晰，层次分明，简单明了，易读易懂。在算法正确的前提下，算法的可读性是摆在第一位的。另一方面，晦涩难读的程序也易于隐藏错误而难以调试。

3、稳健性

算法应对非法输入的数据做出恰当反映或进行相应处理。如果输入非法数据，算法也应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。

4、复杂度

算法效率的度量，是评价算法优劣的重要依据。一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度是指执行算法所需要的计算工作量。空间复杂度是指算法在计算机内执行时所需存储空间的度量。

1、算法的好拍档——数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。

  一、数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1.集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系；

2.线性结构：数据结构中的元素存在一对一的相互关系；

3.树形结构：数据结构中的元素存在一对多的相互关系；

4.图形结构：数据结构中的元素存在多对多的相互关系。

二、数据的物理结构

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

数据元素的机内表示（映像方法）：用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。

关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。

三、数据结构的运算

⑴建立(Create)一个数据结构；

⑵消除(Destroy)一个数据结构；

⑶从一个数据结构中删除(Delete)一个数据元素；

⑷把一个数据元素插入(Insert)到一个数据结构中；

⑸对一个数据结构进行访问(Access)；

⑹对一个数据结构(中的数据元素)进行修改(Modify)；

⑺对一个数据结构进行排序(Sort)；

⑻对一个数据结构进行查找(Search)。

总结：

       在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。

      选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。