算法

解题过程的精确描述。它由有限条可完全机械执行的、有确定结果的指令(或命令、语句)构成并具有以下性质： ①将算法作用于特定的输入集或问题描述上将产生由有限个动作构成的动作序列； ②该动作序列具有惟一的初始动作； ③除末尾的动作外，序列中的每个动作都有一个或多个后继动作； ④序列或者终止于问题的解，或者终止于指出对给定输入集原问题无解。 最常用的算法有排序算法，求解组合问题和组合最优化问题的组合算法等，而动作具有随机性的概率算法可望比确定型算法更高效。随着并行处理机的出现，一类适应于并行操作的并行算法便应运而生，并且日益成为热门的研究领域。 下面用一个例子来解释上述概念。问题描述是：“求实数z的平方根”。该问题的题意明确，但没有指明解的规格。如果满足于把“ ”看成是问题的解，那么，解决此问题的算法再简单不过了：“将根号4--与输人数据z相连接”。如果要求问题的解是精确的十进制表示，那么，2的平方根就永远也算不出来。因为只用“有限”个动作是无法完成的。 如果把问题的描述改为：“求实数x的正平方根，准确到十进制表示的小数点后四位”。这个描述有许多改进：①它指明要求最终解是正根，而先前的那个描述对解的要求是不确定的；②它排除了把“，作为问题解的可能性；③“小数点后四位”提供了测试最终解的规格标准。

对于上述精确描述了的问题的解法可粗糙地表示为：

(1)选择1个数y，计算其平方 (2)若0<y*y-x<5*10e(-5)，T即是所要的解，否则返回到步骤(1)。

这个方法不是上述意义下的“算法”。因为选择y的初值的初始动作是不确定的，而且每个动作的后续动作(即如为何选择y的下一个值)也是不确定的，因此，将上述的过程作用于输入值x后无法得到“惟一确定的一串动作序列”。 若将上述的方法改进为：

(1)选择y。 (2)计算z=y*y。 (3)若 z-x<5*10e(-5)，丁即是所要的解，停止；否则，转到步骤(4)。 (4)用((x／y)+y)／2作为下步的y值；转到步骤(2)。这个过程是牛顿—拉弗森方法的特例。它消除了上述粗糙方法的弊端。并且可以证明，将它作用于任何非负实数x，在有限步之内一定会得到满足解的规格的正平方根。因此，这个过程已经非常接近于前述意义下的“算法”。只是，若将这个解法作用于负实数“，解题过程就会无休止地计算一个又一个的y，永不终结。即动作序列的有限性不能保证(这种不终结的过程称为半算法)。因此，需要对上述方法再作点改进，在它的前面加一步： (0)若z<0，则无解，停止；否则，转到步骤(1)。这样就完美了，称得上是一个完全的“算法”。

上述算法是用自然语言描述的，易于为人所理解。不难用计算机所能接受的PASCAL语言将其改

写成如下的程序：

programSquareRoot(input，output)； var X，Y，Z：real； begin readln(X)； writeln(’Find the square root of，X：0： 0)； if x≥0 then begin Y=1；Z=Y*Y； while abs(X—Z)≥0．00005 do begin Y：= ((X／Y)十Y)／2； Z： =Y*Y end； writeln(The square root of ，X：7： 5，，is，，Y： 7： 5，，•／) end else writeln(There is no square root for， X： 8： 5，，．，)

end这个程序执行时将输入所要求根的数据，然后给出回答：或给出平方根，或指出无解。这个程序对输人数据85，1，0．61 825，-9的相继执行结果是：

Find the square root of 85 The square root of 85．00000 is 9．21 954． Find the square root of 1 The square root of l．00000 is 1．00000． Find the square root of0．61 825 The square root of 0．61 825 is 0．78628． Find the square root of -9 There is no square root for -9．

在上述关于“算法”的严格定义中，我们坚持算法作用于给定的输人数据后所产生的动作序列的惟一性与有限性。惟一性蕴涵着确定性，有限性蕴涵着终止性。确定性指初始动作是确定的，每个动作的后续动作也是确定的(“停止”动作无后续动作)。如果准许每个动作的后续动作可以有有限多种选择，即下一动作是不确定的，这种算法称为不确定算法。例如走迷宫，从其人口到出口，用不确定算法描述起来就比较简单。 设计算法与分析算法是计算机科学的核心问题。从应用范围来看，算法可分成数值算法和非数值算法两大类。从工作方式来看，算法可分成串行算法和并行算法两大类。早在20世纪70年代，D． E．Knuth就指出，计算机科学就是研究算法的学问。因此，将算法这个概念严格化、精确化有重要的实际意义。 任何计算机程序至少是一个半算法，凡能到达“停止”的程序是一个算法(当然未必能解决程序人员心目中的问题)。对于一个给定的问题，可能有许多个算法(程序)，但它们的质量不会全同。衡量程序质量的主要因素是，程序执行所费时间之长短和所需空间(存储容量)之多少。就当今的计算机硬件而言，尤以时间因素为贵。另一个重要的质量因素是算法的一般性问题(即适用范围之大小问题)，如何裁剪一般性主要取决于应用背景。当然还有其他的质量因素，例如，对于数值算法而言，有收敛速度之高低，误差积累之快慢，结果精度之好坏，等等。关于算法的时、空效率参见计算复杂性理论。简言之，将算法概念严格化，既有利于算法设计又有利于算法质量分析。 把算法概念精确化还有深刻的理论意义。原先人们认为，任何合式描述的数学问题都是可计算的。 20世纪20年代开始，数学家对此提出了疑问：问题的“可解性”或函数的“可计算性”到底意味着什么?为了回答这个问题，几十年来建立了许多理论，如图灵机理论、递归函数理论、正规算法理论、A—演算等等，并证明了所有这些理论是等价的：即，一个问题在一个概念下可解，在所有别的概念下也可解。这些研究启示了，算法过程是机械的，发明算法才是人类的创造。