第1章 算法初步

1.1 什么是算法

1.1.1 算法的定义

对算法的解释，从古至今定义是不唯一的。本书给出的算法的定义是：一系列用来解决单个或多个问题，或有执行计算功能的命令的集合。而联系上输入与输出，算法就是将输入转换为输出的一系列计算步骤的集合。生动地讲，可以把一个程序比作一道菜。如图1-1所示，做菜的原材料就是输入，做出来的成品即为输出；而算法，就是做菜过程中的复杂步骤。

算法的本质其实是数学的理论与推导。在还没有发明求和公式之前，如何求出1+2+3+…+n？逐个数求和虽能算出答案，但终究过于繁杂，如果n=10000呢？但反观求和公式，无论n取多大的值，计算的步骤和繁琐程度基本不会增加。这就是算法存在的意义。人类在解决复杂问题时所采用的一系列特定的方法，即为算法。

1.1.2 算法与程序的区别

算法和程序的定义有很大交集。通常来说，（计算机）程序指一组计算机能识别和执行，并有一定功能的指令。后者的定义似乎和算法很相似，但两者最大的区别在于程序是以计算机能够理解的各式各样的编程语言编写而成的，而算法是可以通过编程语言、图绘、口述等人能够理解的方式来描述的，不一定局限于编程语言的诠释，如图1-2所示。不过，算法和程序之间并没有明确的分界线，理解二者的意思就足够了。

刚才曾提过，算法是一种以数学为本质的计算方法。然而作为方法，则必有正确（可行）、不正确（不可行），高效、低效之分。若一个算法对每一个恰当的输入（严格地符合问题的前提条件，且可以为空）都以正确的输出终止程序，则可以称该算法是正确的，并正确地解决了给定的问题。若算法以不正确的输出而终止程序，或根本无法终止程序（如程序陷入死循环），则这个算法是不正确的。

但显而易见，不是所有的算法都可以通过输入和输出的正确和不正确而简单地分为两大类。譬如人们要预测未来特定事件发生概率，而这种问题无法用结果来检验解决方法正确与否。因此，算法的正确性的检验也可以回溯到其本质，就是数学的检验，也就是说用数学来证明算法的正确性或可行性。

对算法至关重要的不只有其正确性，还有它的效率。人类至今的发展，提高最迅速的可以说就是计算的效率了。从原始人的结绳计数，到现在的超级计算机，计算能力的提升不是区区几个数量级能说明的。但很不幸，当今计算机的运算速度不是无限快，存储器也不是免费的，所以如何高效地利用好有限的时间和空间就是算法存在的意义。有趣的是，求解相同问题而设计的不同算法在效率方面通常有显著的差异，而这些算法效率上的差异要比在硬件或者软件效率上的差异大得多。

回到1+2+3+…+n这个求和问题中。一定程度上说，逐个数相加也可以被看作一种解决求和问题的算法，一种简单、低效的算法。相反，求和公式则是一种较复杂、高效的算法。但如何来评判一个算法是否高效？时间复杂度和空间复杂度就是很好的丈量工具。