有哪些算法设计与方法？

要制定一个算法，一般要经过设计、确认、分析、编码、检查、调试、计时等阶段，因此学习计算机算法必须涉及这些方面的内容。在这些内容中有许多都是现今重要而活跃的研究领域。为便于区别，把算法学习的内容分成五个不同的方面：

（一）何设计算法

设计算法的工作是不可能完全自动化的。本书是要使读者学会已被实践证明是有用的一些基本设计策略。这些策略不仅在计算机科学，而且在运筹学、电气工程等多个领域都是非常有用的，利用它们已经设计出了很多精致有效的好算法。读者们一旦掌握了这些策略，也一定会设计出更多新的、有用的算法。

（二）如何表示算法

语言是交流思想的工具，设计的算法也要用语言恰当地表示出来。本书基本采用结构程序设计的方式，选择了一种名为SPARKS的程序设计语言来简单明了地表示算法。至于结构程序设计的内容本书并不打算具体介绍，而是将所能收集到的那些主要结构用于本书所给出的算法之中，只是在本章的最后一节详细讨论了一种非常重要的结构——递归。

（三）如何确认算法

一旦设计出了算法，就应证明它对所有可能的合法输入都能算出正确的答案，这一工作称为算法确认(algorithm validation)。要指出的是，用SPARKS所描述的算法还不足以是一个可以立即投入机器运行的程序。确认的目的在于使我们确信这一算法将能正确无误地工作，而与写出这一算法所用的程序语言无关。一旦证明了算法的正确性，就可将其写成程序，在将程序放到机器上运行之前，实际上还应证明程序是正确的，即证明程序对所有可能的合法输入都能得到正确的结果，这一工作称为程序证明(program proving)。这一领域是当前很多计算机科学工作者集中研究的对象，还处于相当初期的阶段。在这一领域的工作还没取得突破性的进展之前，为了增强对所编制程序的置信度，只能用对程序的测试来权宜代替。

（四）如何分析算法

在前面对有穷性的讨论中，曾提及只应把能在相当有穷步内终止的算法实际投入计算机运行。细心的读者可能当时就会觉得“相当”一词用得非常含糊，能否对有穷步给出一个数量界限呢?这实际上是我们要在这里回答的问题。执行一个算法，要使用计算机的中央处理器(CPU)完成各种运算，要用存储器来存放程序和数据。算法分析(analysis of algorithms)是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法不仅可以预计所设计的算法能在什么样的环境中有效地运行，而且可以知道在最好、最坏和平均情况下执行得怎么样，还可以使读者对解决同一问题不同算法的有效性作出比较判断。关于算法分析更确切的表征将在下一节讨论。

（五）如何测试程序

    测试程序实际上由调试和作时空分布图两部分组成。调试(debugging)程序是在抽象数据集上执行程序，以确定是否会产生错误的结果，若有，则修改程序。但是，这一工作正如著名计算机科学家迪伊克斯特拉(E.Dijkstra)所说的那样，“调试只能指出有错误，而不能指出它们不存在错误。”尽管如此，在程序正确性证明还没取得突破性进展的今天，调试仍是不可缺少且必须认真进行的一项重要工作。作时空分布图是用各种给定的数据执行调试认为是正确的程序，并测定为计算出结果所花去的时间和空间，以印证以前所作的分析是否正确和指出实现最优化的有效逻辑位置。

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=8