1.3 算法

下面用一道例题来说明不同的算法效率不同。

【例1-1】找假币：假设n（n≥2）枚硬币中有一枚为假币，假币比真币轻，怎样才能找出假币？

方法1：一个个比较硬币，直到找出假币为止。假设n=10，首先比较硬币1和硬币2，会出现两种情况。

● 如果重量不一样，较轻者即为假币。

● 如果重量一样，则选取两枚中任意一枚与其他的硬币比较。

如上依次比较硬币3、4、5……，直到找出假币。在最差的情况下，比较9次才能找出假币。即从n枚硬币中找出假币，需要比较n-1次，比较过程如图1.3所示。

方法2：方法1中，若两枚硬币重量一样，说明都是真币，无须再进行比较。因此，将n枚硬币每两枚分为一组进行比较，会出现两种情况。

● 如果重量不一样，较轻者即为假币。

●如果重量一样，就继续比较下一组的两枚硬币。

如上依次进行比较，直到找出假币。在最差的情况下，比较5次就可找出假币。即从n枚硬币中找出假币，需要比较n/2次，比较过程如图1.4所示。

方法3：方法2中，既然所有真币重量一样，将n枚硬币分为两组进行比较，有假币的一组必然轻些；再将较轻的这一组等分为两组进行比较，以此类推，直到找出假币。从n枚硬币中找出假币，需要比较log₂ n次。10枚硬币比较过程如图1.5所示。

可以看到，方法3比较的次数最少，不同的方法（算法）效率差距很大。

1.3.1 算法的5个属性

算法是解决一个问题而采取的方法和步骤，是对解题方案的准确而完整的描述，是一系列解决问题的清晰指令。通过一定规范的输入、处理，在有限时间内获得输出的整个过程，算法与具体的程序语言无关，具备以下5个特性。

● 确定性。算法的每个步骤都应确切无误，没有二义性。

● 可行性。算法的每个步骤都必须满足计算机语言能够有效执行、可以实现的要求，并可得到确定的结果。

● 有穷性。算法包含的步骤必须是有限的，并可以在一个合理的时间限度内执行完毕，不能无休止地执行下去。例如，计算圆周率，只能精确到小数点后某一位。

● 输入性。由于算法的操作对象是数据，因此应在执行操作前提供数据，执行算法时可以有多个输入，例如，求两个整数m和n的最大公约数，则需要输入m和n的值；当然也可以没有输入，例如，求4！等。

● 输出性。一般提供1个或多个输出。

【例1-2】从键盘输入三角形的3条边，求三角形的面积。

【解析】其算法步骤如下所述。

1）从键盘任意输入3个整数，用a、b、c存储。

2）判断a、b、c是否符合三角形的定义（两边之和大于第三边）。

3）如果符合三角形定义，先求出周长的一半s=（a+b+c）/2，再调用海伦公式，area=，求出三角形面积area。

4）输出area。

下面，用算法的5个特性来分析【例1-2】。

● 确定性。【例1-2】共有4个步骤，每一个步骤都有确定的含义，没有二义性。

●可行性。【例1-2】的每个步骤都可以用高级程序设计语言，如Python语言或C语言等实现。

● 有穷性。【例1-2】只有4个步骤，是有限的。

● 输入性。【例1-2】有3个输入，a、b、c分别代表三角形的3条边。

● 输出性。【例1-2】有一个输出，area代表三角形的面积。

1.3.2 算法的3个层次

算法是程序设计的核心内容。算法的学习大致分为3个层次，如表1.1所示。

第一层是“算法基础教学阶段”，涉及基本的算法和程序设计方法，如查找、排序和递归程序设计等。典型的课程是 《数据结构》。

第二层是“算法提高教学阶段”，涉及重要的算法设计方法，如分治法、动态规划法、贪心法和回溯法等，理解算法的时间和空间复杂度，以及复杂度分析等重要概念。典型的课程是 《算法设计与分析》。

第三层是“算法高级教学阶段”，涉及工程应用中和数据智能处理相关的一些重要算法和模型，如最优化方法（如梯度下降法）、遗传算法和神经网络算法等。典型的课程是 《工程最优化方法》 《模式识别》 《人工智能》 等。

按照算法的3个层次进行递进式学习，一般会经历阅读与分析程序、模仿编程、掌握常见程序模块、简单编程及复杂编程等过程，学习步骤如下所述。

1）学习一门语言，如C、C++、Python和Java。

2）熟悉基本的算法，如查找、排序等。

3）掌握数据结构，特别是树和图。

4）在各种刷题网站上进行实践练习，具体网址如下。

https://leetcode-cn.com/problemset/algorithms/

https://www.luogu.com.cn/training/mainpage

https://vjudge.net/contest

http://codeforces.com/contests

http://acm.hdu.edu.cn/

http://bestcoder.hdu.edu.cn/