计算机算法

用于解释软件的一个流行的比喻是把它比作烹调用的菜谱。用于某些菜肴的菜谱列出了所需的配料，烹饪所必需的一系列操作，以及期望的结果。通过类比可知，一个用于完成某些任务的程序需要数据来操作，而且阐明对这些数据要做什么。真正的菜单相对编程而言太模糊且容易有歧义，因此用来类比并不是特别好。例如，一个巧克力蛋糕的菜单是这样写的：“在炉子里烘焙30分钟或者直到它完成。

把你的手轻轻地平放在蛋糕的表面进行测试。”那么测试人员应该寻找什么呢？——摆动、阻力或者是其他的什么？“轻轻地”是如何轻呢？烘焙时间是至少30分钟还是不超过30分钟？税单是一个更好的比喻：它们详细明了地说明要做什么。这个类比仍然不够完美，但是税单抓取的计算方面比菜谱做得好：需要算术运算，数据值可以从一个地方拷贝到另外一个地方，条件可以测试，后续的计算依赖于前者的结果。尤其对于税单而言，应该完成这个过程——无论什么情况下总是应该产生结果，到期应纳税款的总和。这不应该是模糊不清的，任何人从相同的初始化数据开始都应该得到相同的最终答案。

使用一段时间后应该停止。从个人的经验而言，这些都是理想化的，因为用词并非总是清晰，计算说明比税务机关愿意承认的更模糊，使用什么样的数据值经常也不是很清楚。算法是一个仔细、精确、不模糊的菜谱或税单的计算机科学版本，是确保计算出正确结果的一系列步骤。每一个步骤都用基本操作来表达，这些操作的含义都是完整定义的，例如“将两个整数相加”。所有事情的含义没有不清楚的。输入数据的类型已经给定。所有可能的情况已经覆盖；算法绝不会遇到不知道下一步做什么的情况。以学究式的态度，计算机科学家通常会增加另外一个条件：算法必须在最后终止。按照这个标准，经典的洗发指令“打泡、漂洗、重复”并不算是一个算法。

有效算法的设计、分析和实现是学院派计算机科学的核心部分，并且还有很多真实世界的重要算法。我不打算试图精确地解说和表达算法，但是我的确想表达这样一个想法，用足够的细节和精度指定一个操作序列，这里对操作的含义以及如何执行它们不存疑问，即使它们由没有智力或想象力的实体来执行。我们还将讨论算法的效率，也就是说计算时间如何依赖于要处理的数据量。我们会用一些基本的算法来讲解，这些算法都是常见且容易理解的。