1.3 算法的基本概念

1.3.1 算法及其重要特性

1.什么是算法

算法（algorithm）被公认为是计算机科学的基石。通俗地讲，算法是解决问题的方法。现实生活中关于算法的实例不胜枚举，如一道菜谱、一个安装转椅的操作指南等，再如四则运算法则、算盘的计算口诀等。严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列，如图1-15所示。此外，算法还必须满足下列五个重要特性：

图1-15 算法的概念

（1）输入：一个算法有零或多个输入（即算法可以没有输入），这些输入通常取自某个特定的对象集合。

（2）输出：一个算法有一或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。

（3）有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。

（4）确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。

（5）可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

算法和程序不同。程序（program）是对一个算法使用某种程序设计语言的具体实现，原则上，算法可以用任何一种程序设计语言实现。算法的有穷性意味着不是所有的计算机程序都是算法。例如操作系统是一个在无限循环中执行的程序而不是一个算法，然而我们可以把操作系统的各个任务看成是一个单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，得到输出结果后便终止。

2.什么是“好”算法

一个“好”算法首先要满足算法的五个重要特性，此外还要具备下列特性：

（1）正确性：指算法能满足具体问题的需求，即对于任何合法的输入，算法都会得出正确的结果。

（2）健壮性：指算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。

（3）可理解性：指算法容易理解和实现。算法首先是为了人的阅读和交流，其次是为了程序实现，因此，算法要易于人的理解、易于转换为程序。晦涩难懂的算法可能隐藏一些不易发现的逻辑错误。

（4）抽象分级：算法一旦创建，必须由人来阅读、理解、使用和修改它们。而研究发现，对大多数人来说，人的认识限度是7±2。如果算法涉及的想法太多，人就会糊涂，因此，必须用抽象分级来组织算法表达的思想。换言之，算法中的每一个逻辑步骤可以是一条简单的指令，也可以是一个模块，通过模块调用完成相应功能。每个模块表示一种抽象，模块的内部描述了怎样实现抽象，而模块的名称描述了模块的功能。

（5）高效性：算法的效率包括时间效率和空间效率，时间效率显示了算法运行得有多快；而空间效率则显示了算法需要多少额外的存储空间。不言而喻，一个“好”算法应该具有较短的执行时间并占用较少的辅助空间。

1.3.2 算法的描述方法

算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。下面以欧几里得算法为例进行介绍。

1.自然语言

用自然语言描述算法，最大的优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长。欧几里得算法用自然语言描述如下：

步骤1：将m除以n得到余数r；

步骤2：若r等于0，则n为最大公约数，算法结束，否则执行步骤3；

步骤3：将n的值放在m中，将r的值放在n中，重新执行步骤1。

2.流程图

用流程图描述算法，优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。欧几里得算法用流程图描述如图1-16所示。

图1-16 用流程图描述欧几里得算法

在计算机应用早期，使用流程图描述算法占有统治地位，但实践证明，除了描述程序设计语言的语法规则和一些非常简单的算法，这种描述方法使用起来非常不方便。

3.程序设计语言

用程序设计语言描述的算法能由计算机直接执行，而缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。欧几里得算法用C语言书写的程序如下：

            #include＜stdio.h＞
            intCommonFactor（intm，intn）
            {
              intr=m% n；
              while（r！=0）
              {
                  m=n；
                  n=r；
                  r=m% n；
              }
              returnn；
            }
            intmain（）
            {
              printf（＂最大公约数是：%d/n＂，CommonFactor（35，25））；
              return0；
            }

4.伪代码

伪代码（pseudo-code）是介于自然语言和程序设计语言之间的一种方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。至于算法中自然语言的成分有多少，取决于算法的抽象级别。抽象级别高的伪代码自然语言多一些，抽象级别低的伪代码程序设计语言的语句多一些。欧几里得算法用伪代码描述如下：

上述伪代码可以再具体一些，一般采用某种程序设计语言的一个核心子集。本书采用C语言的基本语法和控制结构，为了便于描述算法，对C语言做了若干扩充和修改，具体如下：

（1）用函数来描述算法，并且不用在主函数中调用函数；

（2）增加了C++语言的引用参数传递方式，在形参表中以符号“&”开始的参数即为引用参数；

（3）当算法出现异常时，使用语句“exit（-1）；”结束算法的执行并将状态码-1返回；

（4）不用包含头文件，输入/输出语句可以省略格式控制符；

（5）局部变量可以不声明；

（6）用符号“←→”表示交换两个变量的值。

采用C语言的函数来描述算法，使得算法的描述简明清晰，既不拘泥于C语言的实现细节，又容易转换为C/C++程序。欧几里得算法的C语言描述如下：

            intCommonFactor（intm，intn）
            {
              r=m% n；
              while（r！=0）
              {
                m=n；
                n=r；
                r=m% n；
              }
              returnn；
            }

伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化了描述算法的不必要的技术细节，是比较合适的描述算法的方法，被称为“算法语言”或“第一语言”。