1.4.1 算法及其设计基本准则

算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。例如，求解的问题可以是对给定的一组数据进行排序，或求一元二次方程的解，算法就是对这类问题求解过程或步骤的说明。一个算法应该具有下列特性。

●有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。

●确定性。算法的每一步必须有确切的定义，无二义性。在算法执行中，相同的输入仅有唯一的一条执行路径。

●可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。

●输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。

●输出。一个算法具有一个或多个输出，这些输出与输入之间存在某种特定的关系。

算法的含义与程序相似，但又有区别。一个程序不一定满足有穷性。例如，计算机操作系统本身就是一个程序，只要整个系统不遭破坏，就永远不会停止，即使没有作业需要处理，它也会处于动态等待中。因此，操作系统不是一个算法。另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止，这意味着不是所有的计算机程序都是算法。

在本门课程的学习、作业练习、上机实践等环节，算法都用C++语言来描述。在上机实践时，为了检查算法是否正确，可以通过编写完整的C++语言程序来实现算法。

算法与数据结构相辅相成。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。

要设计一个好的算法，通常要考虑以下要求。

●正确性。算法的执行结果应当满足预先规定的功能和性能要求。它有4层含义，即不含语法错误，对多组数据运行正确，对典型、苛刻的数据运行正确，以及对所有数据运行正确。

●可读性。算法主要是为了阅读与交流，其次才是为计算机执行，因此算法应该易于理解；而晦涩难读的程序容易隐藏较多错误，导致难以调试。所以，算法应当思路清晰、层次分明、简单明了、易读易懂。

●健壮性。当输入的数据非法时，算法应当恰当地做出反应或进行处理，而不是产生不正确的输出结果；应能进行适当处理，不致引起严重后果。

●高效性。有效使用存储空间和有较高的时间效率。