设计算法

计算机学术语

对算法的学习包括5个方面：设计算法、表示算法、确认算法、分析算法、验证算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域。设计算法的原则包括：正确性、可读性、健壮性、高效率与低存储量。

定义

算法就是为解决问题而采取的方法与步骤。随着计算机的出现，算法被广泛地应用于计算机的问题求解中，被认为是程序设计的精髓。对算法的学习包括5个方面：设计算法、表示算法、确认算法、分析算法、验证算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域。

原则

对于一个特定问题的算法在大部分情况下都不是唯一的。也就是说，同一个问题，可以有多种解决问题的算法，而对于特定的问题、特定的约束条件，相对好的算法还是存在的。因此，在特定问题、特定的条件下，选择合适的算法，会对解决问题有很大的帮助；否则前人的智慧我们不能借鉴，凡事就都得自己从头研究了，这就是所谓的要去“发明轮子”。

在设计算法时，通常要考虑以下原则：

正确性

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需要、能够得到问题的正确答案。

但是算法的“正确”通常在用法上有很大的差别，大体分为以下4个层次：

（1）算法程序没有语法错误；

（2）算法程序能够根据正确的输入的值得到满足要求的输出结果；

（3）算法程序能够根据错误的输出的值满足规格说明的输出结果；

（4）算法程序对于精心设计、极其刁难的测试数据都能满足要求的输出结果。

对于这4层含义，层次（1）要求最低，因为仅仅没有语法错误实在谈不上是好的算法。而层次（4）是最困难的，人们几乎不可能逐一验证所有的输入都得到正确的结果。

因此，算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，人们把层次（3）作为一个算法是否正确的标准。

可读性

设计算法的目的，一方面是为了让计算机执行，但还有一个重要的目的就是为了便于他人的阅读，让人理解和交流，自己将来也可阅读。如果可读性不好，时间长了自己都不知道写了什么，可读性是评判算法（也包括实现它的程序代码）好坏很重要的标志。可读性不好不仅无助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现并且难以调试和修改。

健壮性

当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是莫名其妙的输出结果。并且处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便于在更高的抽象层次上进行处理。

高效率与低存储量

通常，算法的效率指的是算法的执行时间；算法的存储量指的是算法执行过程中所需要的最大存储空间，两者的复杂度都与问题的规模有关。算法分析的任务是对设计的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性。

在满足以上几点以后，还可以考虑对算法进程进一步优化，尽量满足时间效率高和空间存储量低的需求。

步骤

设计算法的一般过程可以归纳为以下几个步骤：

建立数学模型

通过对问题进行详细的分析，抽象出相应的数学模型。

确定数据结构与算法

确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法。

选用语言