1.2 算法

1.2.1 算法概念

美国分析哲学家鲁道夫·卡尔纳普（Rudolf Carnap）在《世界的逻辑构造》一书中认为：事物既不是“被产生的”，也不是“被认识的”，而是“被构造的”。构造的过程从计算科学的角度看就是算法实施的过程，也就是计算的过程，自然界这本大书是用算法语言写的！宇宙是一个巨大的计算系统！ 对于自然（人工）现象的物理抽象是将问题单纯化，成为一个验证体系；数学抽象是将问题逻辑化，成为一个推理系统；而计算抽象是将问题符号化，成为一个计算系统。计算思维之魂就是算法，计算思维的核心是算法思维。

采用算法思维求解问题可分为以下几个基本步骤：

（1）问题的抽象；

（2）问题的符号化表示；

（3）问题求解的算法；

（4）算法的实现。

以著名的哥尼斯堡七桥问题为例，数学家欧拉将它抽象为一个数学问题，即经过图中每条边一次且仅一次的回路即欧拉回路（路径）问题。这种抽象分为两个阶段：

（1）简化：七桥——点、线、图；

（2）泛化：无向图的欧拉路径。

计算机科学家会怎么解决这个问题呢？首先把它抽象成一个符号系统：一个图是一个顶点集和一个边集组成的偶对。判断这个图中是否存在欧拉路径，首先要构造一个算法，再用这个算法去找欧拉路径，如果算法成功了，就能找出欧拉路径。否则，这个图中不存在欧拉路径。在这里我们可以看到数学思维与计算抽象存在一个极大的不同，数学抽象给了我们一个判断的规则，我们自己去推有没有。计算思维给了我们一个算法去找，如果有就能把它找出来了，如果没找出来就说明没有。

算法（Algorithm）是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地讲，就是计算机解题的步骤。

一个算法应该具有以下五个重要特征。

（1）有穷性：一个算法必须保证执行有限步之后结束。

（2）确定性：算法的每一步骤必须有确定的定义。

（3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。0个输入是指算法本身给定了初始条件。

（4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。

（5）可行性：算法上描述的操作在计算机上都是可以实现的。

虽然设计一个好的求解算法更像是一门艺术，而不像是一项技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。在一般情况下，为了获得较好的性能，必须对算法进行细致的调整和优化。但是在某些情况下，调整和优化之后算法的性能仍无法满足要求，这时就必须寻求其他的方法来求解。

算法的复杂性用复杂度来说明，分为时间复杂度和空间复杂度。

时间复杂度：执行该算法所需要的计算工作量，一般用所需基本运算的执行次数来度量。

空间复杂度：执行该算法所需的内存空间，一般用算法程序本身占的空间+输入的初始数据占的空间+算法执行过程中所需的额外空间的总和来表示。

1.2.2 算法效率

先看一个例子。学校教务中心有一个学生数据库，可以从中检索学生的各种信息。假设现在要打印自动化专业31班学生的花名册，并且假定班上有50名学生，要求花名册按照学生姓名的拼音顺序排列。下面看一下不同的程序设计（算法实现）所得到的不同的检索效率。

一个直接的算法是将50 名学生所有可能排列的表都打出来，然后从中挑选一张符合拼音顺序的表。我们知道，50个人的不同排列有50！种，即这样的表有50！张，这个数目之大，用每秒100万次的计算机不停地运算需要9.6 × 1048个世纪，显然，用排列组合方式构造的检索方法是不能实施的。

因此，需要设计一个算法来提高程序的检索效率，也就是常用的排序算法。

随机地将50名同学的名字排列在一起，也就是说初始无序。

取第二位同学的名字依拼音顺序和第一位的名字比较一次，如果顺序，则仍然放在第二的位置，否则交换它们的位置，使之顺序。

现在开始比较第三位，第三位则需要和前两位的名字至多比较两次，至多交换两次。

依次类推，第k位至多要比较k − 1次，第50位至多需要比较49次，至多交换49次。于是，比较和交换次数最多都是1 + 2 + … + 49 = 49 × 50 / 2 = 1225次，这样就完成了排序过程。

当参加排序的个数是n时，第一种算法需要运算n！（当n＞25时，n！＞10n）次，第二种算法至多需要运算（n − 1）n/2次，约是n2数量级。前者的次数随n的增加，按照10n的指数方式增加，后者则只按n的二次多项式的方式增加。一般地，假如在一个问题中有n个数据需要处理，而处理的算法的计算次数以指数n方式增加，则称为指数算法；若按n的多项式方式增加，则称为多项式算法。显然，寻找各种问题的多项式算法，是数学发展的一个重大的关键点。

因此，算法的优劣程度决定了程序执行效率的高低。