[科普中国]-算法正确性

定义

算法是可供计算机执行的对数据进行处理的一个有穷步骤，是解决问题的一个逻辑顺序，是解题方法的精确描述，它有一些精确定义的操作规则，每条规则是确定的、能行的，不能有二义性。算法有一个初始输入，它给出最原始的条件，并且有一个最终的算法输出，它给出算法的目标，同时每个算法需有一个算法名。

算法正确性是对任意一个合法的输入经过有限步执行之后算法应给出正确的结果。其中“正确”的含义包括以下三个方面：

(1)算法对几组不同的输人数据能够得出满足要求的结构。

(2)算法对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足要求的结果。

(3)算法对于一切合法的输入数据都产生满足要求的结果。2

算法正确性证明包括两个方面：①证明关于输入与输出之关系的命题是正确的；②证明算法中的公式及计算方法是正确的。

正确性是对算法最基本、最重要的要求。1

证明如果一个算法对于所有合法的输入，都能在有限时间内输出预期的结果，那么此算法是正确的。确认一个算法是否正确的活动称为算法确认(algorithm validation）算法确认的目的在于确认一个算法能否正确无误地工作。使用数学方法证明算法的正确性，称为算法证明(algorithm proof ）对于有些算法，正确性证明十分简单，但对于另一些算法，却可能十分困难。

证明算法正确性常用的方法是数学归纳法。若要表明算法是不正确的，只需给出能导致算法不能正确处理的输入实例即可。

到目前为止，算法的正确性证明仍是一项很有挑战性的工作。在大多数情况下，人们通过程序测试和调试来排错。程序测试(program testing)是指对程序模块或程序总体，输入事先准备好的样本数据(称为测试用例，test case)，检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活动。测试的目的是为了“发现错误”而不是“证明程序正确”。程序经过测试暴露了错误，需要进一步诊断错误的准确位置，分析错误的原因，纠正错误。3

算法设计其他要求可读性算法主要是为了方便程序员的阅读与交流，其次才是便于机器执行。可读性好有利于程序员对算法的理解；晦涩难懂的程序易隐藏较多错误，难以调试和修改。

健壮性健壮性即指算法对于非法输入的抵抗能力，它强调了即使输入了非法数据，算法应能够识别并做出正确处理，而不是产生莫名其妙的输出结果。例如，一个求凸多边形面积的算法是采用求各三角形面积之和的策略来解决问题，当输入的坐标值集合表示的是一个凹多边形时，则不应继续计算，而应报告输入出错。并且，处理错误的方法是返回一个表示错误或错误性质的值，而不是打印错误信息或异常，并同时终止程序的执行，以便在更高的抽象层次上进行处理。

高效率和低存储量算法的效率通常是指算法的执行时间。对于一个具体的问题，通常有多个算法可以解决，执行时间短的算法其效率就高。所谓存储量，是指算法在执行过程中所需要的最大存储空间。效率与低存储量需求这两者与问题的规模有关。2