4.4 算法

用计算机解题时，算法是编程的基础。如果问题不是非常简单，就必须先设计出正确的算法，然后才可以编写程序。否则往往会事倍功半，甚至返工重来。高质量的程序离不开好的算法，设计算法是程序设计中非常关键的环节。

4.4.1 算法的概念与特点

在日常工作、学习和生活中，为了完成一个任务，都需要按照特定的步骤序列进行。比如做饺子吃的步骤为：①准备饺子皮；②准备饺子馅；③包饺子；④煮饺子；⑤吃饺子。这个过程中某些步骤的先后顺序是不能颠倒的，比如必须先准备饺子皮和准备饺子馅，然后才能包饺子，接着才能煮饺子，最后才能吃饺子。再比如工厂产生产品的步骤为：①设计产品；②生产产品；③测试产品。

在程序设计中，算法是实现一个功能的有限步骤序列。

算法具有以下5个特点：

①确定性。算法的每一步功能是确定的，不能有二义性。自然语言中经常出现二义性，比如:介于100和200之间的偶数有哪些？有些人认为该问题包括100和200，另外有些人则认为不包括100和200。

②有穷性。算法的执行步骤是有限的。因为只有步骤有限才具有实用价值。有穷性的另一个含义是，算法必须在用户要求的时间内完成，否则也是没有意义的。

③可行性。算法的每一步在计算机上是能够实现的。比如，在C语言中，两个字符串是不能进行乘法运算的。

④零个或多个输入。算法的功能是处理原始数据得到结果。通常，设计算法时，原始数据无法确定，执行算法时，再输入原始数据。比如例4-14需要执行算法时输入10个数据。特殊情况下，设计算法时，原始数据已经确定，执行算法时，无需输入，比如显示从100到200之间的全部素数。

⑤一个或多个输出。算法执行后应该有一个或多个结果，即输出。

4.4.2 算法的描述方法

常见的描述算法的方法有自然语言、程序流程图、计算机语言、伪代码和N-S图。每种方法都有各自的优缺点，不存在一种十全十美的方法。

1.自然语言

用自然语言描述算法容易理解，但是容易出现二义性。例4-1和例4-14都采用自然语言描述算法。

2.程序流程图

程序流程图是一种传统的描述算法的方法，目前仍被许多人采用。其最大优点是能够直观显示算法的控制流程。程序流程图使用基本图形符号表示算法的执行过程

3.计算机语言

用计算机语言表示算法，即编程。该方法的主要优点是算法描述准确，无二义性。主要缺点是，因为计算机语言具有严格的语法限制，用计算机语言描述算法时，许多精力被用在了计算机语言的繁杂细节上。而算法的重点应该是处理数据的过程。

4.伪代码

用自然语言描述算法，容易理解，但容易出现二义性。用计算机语言描述算法，准确无二义性，但却被计算机语言复杂的语法细节所烦扰。伪代码是一种介于计算机语言和自然语言之间的算法描述方法，具有计算机语言的准确无二义性和自然语言的容易理解的优点。

4.4.3 算法复杂度

算法执行时性能的好坏用算法复杂度衡量。算法复杂度包括时间复杂度和空间复杂度。

1.时间复杂度

算法时间复杂度就是算法执行时所需的时间。只有将算法用某种计算机语言实现（即编程），然后才能在计算机硬件上执行程序。显然执行时间与计算机硬件、计算机语言和程序员水平有关。为了衡量算法本身性能，应该忽略计算机硬件、计算机语言和程序员水平等因素。为简单起见，通常使用算法中基本运算的次数来衡量时间复杂度。

2.空间复杂度

算法的空间复杂度是指算法执行时所需要的内存空间，包括保存程序的空间和保存数据的空间。由于现代计算机的内存空间很大，除非是个别的大型运算，多数情况下不再考虑空间复杂度。

4.4.4 算法设计基本方法

下面介绍几种常见的算法设计方法，这些方法之间往往存在着一定的联系。本部分的算法统一使用Raptor描述。

1.穷举法

穷举法也称枚举法，基本思想是根据问题的部分条件确定一个包含所有解的大致范围，然后对该范围中的每种情况判断是否满足问题的条件，如果满足就是问题的一个解。穷举法的关键点有两个，即穷举的范围和解的条件。

2.回溯法

回溯法的基本思想是通过搜索试探解决问题。首先分析问题，找出解决问题的线索，然后从起点沿着这个线索逐步试探，成功一步就前进一步，若到达了目标状态，就得到了问题的解；若试探失败，则逐步回退，再试探别的路线。

3.递归法

所谓递归就是一个过程直接或间接地调用自己。其基本思想是把一个问题划分为若干个性质相同但规模缩小了的子问题。使用递归法，关键点有两个，一个是确定子问题，另一个是确定边界条件，即不再调用自己的的条件。

4.分治法

算法的时间复杂度是问题规模n的函数，对于O(n²)、O(2ⁿ)和O(n!)这样的复杂度，随着n的增长，运算量将快速增长。分治法的思想是将规模大的问题分解为若干个规模小的独立子问题，然后分别对每个子问题进行求解，最后合并各个子问题的解，即可获得原问题的解。在很多情况下，子问题的性质与原问题相同，只是规模变小了，这时也可以使用递归法。

5.贪心法

贪心法是指在对问题求解时，总是根据眼前的条件做出选择，而不是从整体考虑进行选择。贪心法不保证得到最优解，但是在很多情况下可以得到近似最优解。

6.动态规划法

动态规划法是将待求解问题分解成若干个子问题，而子问题之间往往不是独立的，这时如果采用分治法或递归法求解，子问题的重叠部分就会被重复计算。作为改进，动态规划法在求解子问题时，将子问题的结果保存到一个表格中。以后需要再次求解该子问题时，只需查表即可得到结果，避免了大量的重复计算。