程序算法艺术与实践:基础知识之有关算法的基本概念

对于给定的问题，一个计算机算法就是用计算机求解这个问题的方法。一般来说，算法是由有限条指令构成，每条指令规定了计算机所要行的有限次运算或者操作。对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的设计。 算法的基本特征作为一个算法，一般应具有以下几个基本特征。 - 可行性（effectiveness) 针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的 限制，使执行结果产生偏差。例如，在进行数值运算时，如果某计算工具有7位有效数字（如程序设计语言中的单精度运算），则在计算下列三个量A=1012，B=1，C= —1012的和时，如果采用不同的运算顺序，就会得到不同的结果，即：A+B+C=1012+1+（—1012）=0   A+C+B=1012+（—1012）+1=1 而在数学上，A+B+C与A+C+B是完全等价的。因此，算法与计算公式是有差别的。在设计一个算法时，必须考虑它的可行性，否则是不会得到满意结果的。 - 确定性 (definiteness)算 法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解 决实际问题时，可能会出现这样的情况：针对某种特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从。这是因为根据数学 公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，此计算过程就不能适应了。 - 有穷性 (finiteness) 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数值的过程只能是有穷的。因此，一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应该包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，显然失去了实用价值。 - 拥有足够的情报 一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这 是算法执行的起点或者是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也 就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。 综上所述，所谓算法，是一组严谨的定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 算法的基本要素 一个算法通常有两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 1. 算法中对数据的运算和操作: 每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。 通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下四类：①算术运算：主要包括加、减、乘、除等运算。②逻辑运算：主要包括“与”、“或”、“非”等运算。③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。④数据传输：主要包括赋值、输入、输出等操作。前面提到，计算机程序也可以作为算法的一种描述，但由于在编制计算机程序时通常要考虑很多与方 法和分析无关的细节问题（如语法规则），因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法，而是用别的描述工具（如流程图，专门的算术描述 语言，甚至用自然语言）来描述算法。但不管用哪种工具来描述算法，算法的设计一般都应从上述四种基本操作考虑，按解题要求从这些基本操作中选择合适的操作 组成解题的操作序列。算法的主要特征着重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的演绎数学是以公理系统为基础 的，问题的求解过程是通过有限次推演来完成的，每次推演都将对问题作进一步的描述，如此不断推演，直到直接将解描述出来为止。而计算机算法则是使用一些最 基本的操作，通过对已知条件一步一步的加工和变换，从而实现解题目标。这两种方法的解题思路是不同的。 1. 算法的控制结构 :一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统的流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 算法复杂度主要包括时间复杂度和空间复杂度。 算法的时间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。例如，在考虑 两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算忽略不计。又如，当需要在一个表中进行查找时，可以将两个元 素之间的比较作为基本运算。所执行的基本运算次数还与问题的规模有关。综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数. 算法的空间复杂度 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一 个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中 的工作单元以及某种数据结构所需要的附加存储空间（例如，在链式结构中 ，除了要存储数据本身外，还需要存储链接信息）。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（inplace）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。 关于[程序算法艺术与实践](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多讨论与交流，敬请关注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).