1.2 计算机问题求解的灵魂——算法

1.2.1 算法及其特性

计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。它包括了涵盖计算机科学之广度的一系列思维活动。用计算思维实现问题求解，需要经过以下几个步骤。

（1）对问题进行抽象与映射，将客观世界的实际问题映射成计算空间的计算求解问题，建立解决问题的数学模型。当有多个数学模型可用时，需要对模型进行分析、归纳、假设等优化，选择最优模型。

（2）将建立的数学模型转换成计算机所理解的算法和语言，也就是将数学模型映射或分解成计算机所理解和执行的计算步骤。

（3）编写程序就是将所设计的算法翻译成计算机能理解的指令，即用某一种计算机语言描述算法（这就是计算程序）。然后通过上机实践，完成问题求解。

在这个过程中，我们始终以问题的抽象、问题的映射、问题求解算法设计等为主线展开讨论，编写程序只不过是用一种计算机语言去实施问题求解，而对数学模型进行转换所得到的算法才是计算机问题求解的灵魂。所谓算法（Algorithm），就是一组明确的、有序的、可以执行的步骤集合。算法的概念要求步骤集是有序的，这样就要求算法中的各个步骤必须拥有定义完好的、顺序执行的结构。

算法应具有4个特性：有穷性、确定性、有零个或多个输入、有一个或多个输出。有穷性是指一个算法必须保证执行有限步骤之后结束；确定性是指算法的每一步骤必须有确切的定义，算法步骤必须没有二义性，不会产生理解偏差；有零个或多个输入是指描述运算对象的初始情况，其中零个输入是指算法本身给出了初始条件；有一个或多个输出是指算法必须要有结果。

算法主要分为两类：数值运算算法和非数值运算算法。数值运算算法主要用于解决数值求解问题，例如求方程的根、求函数的定积分、求最大公约数等。非数值运算算法主要用于解决需要用逻辑推理才能解决的问题，常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理、人机围棋大战、定制服务等。

算法分析，一般应遵循以下4个原则。

（1）一个算法必须是正确的，符合计算机所要求解的题目，能得到预期的结果。

（2）求解一个问题，先分析执行算法所需要耗费的时间。

（3）求解一个问题，先分析执行算法所需要占用的存储空间。

（4）编制的算法要求条理清晰、易于理解、易于编码、易于调试。