【精彩书摘】：第1章 绪论
什么是算法？为什么要对算法进行研究？相对于其他信息技术来说，算法的作用是什么？在实际生活中，算法有什么应用价值？衡量一个算法好坏的标准是什么？本章将围绕这些问题展开讨论。
1.1 算法的基本定义
简单来说，所谓算法（algorithm）就是明确的计算过程，它取一个或一组值作为输入，并生成一个或一组值作为输出。亦即，算法就是一系列的计算步骤，用来将输入数据转换成输出结果，
如图1.1所示。
我们还可以将算法看作是一种工具，用来解决可以抽象出计算模型的问题。在表述该问题时，必须用严谨的语言规定所需的输入／输出关系。与之对应的算法则描述了一个特定的计算过程，用于实现这一输入／输出关系，如下所示。
输入：由n个数构成的一个序列（a1，a2，…an）。
输出：输出一个重排的序列（a1`，a2`，…an`）。，使得a1`≤a2`≤…≤an`。
需要指出的是，问题的表述方式是多样化的，并不一定像上面例子这么抽象呆板，例如，许多试题就采用了生动趣味的故事形式。而这里所说的语言严谨，是针对抽象计算模型而言。也就是说求解的目标是什么，给出了哪些已知信息、显式条件或隐含条件，最后应该用什么样的数据形式表达计算结果，必须描述清楚，切不能模棱两可或者产生歧义。同样，与问题对应的计算过程可以用自然语言、程序设计语言甚至硬件设计等形式来表达。不论采用哪种形式，解决问题的每一个步骤都必须准确定义，这是由于我们是和计算机打交道，稍有含糊则风马牛不相及。自然语言传递的信息，从语意上来看，可能会有不明之处，但我们处理它们时可根据上下文信息或平时习惯等来推理并准确地接受它，而计算机却不能。尤其是编程时，要用程序设计的范式语言精
确定义每一个步骤，千万不要误以为自己懂了计算机也会懂。
我们衡量一个算法好坏的标准主要有两个：正确性和时效性。
（1）算法的正确性。如果一个算法使其每一个输入实例都能在输出正确的结果后停止，则称它是正确的。
……
...
发表于 2008-11-28 01:42
