算法的基本概念

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。

4.1.1　算法的特征

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

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

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

（3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。

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

（5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

4.1.2　算法的表示方法

算法通常有3种表示方法：自然语言法、程序流程图法、程序法。

结构化程序设计三种程序结构的流程图（N-S图）如下。

（1）顺序结构（见图4.1）。

（2）选择结构（见图4.2）。

（3）循环结构。

当型循环（见图4.3），直到型循环（见图4.4）。

图4.1　顺序结构

图4.2　选择结构

图4.3　当型循环

图4.4　直到型循环

4.1.3　算法分析——算法的复杂性

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源，所需的资源越多，我们就说该算法的复杂性越高；反之，则该算法的复杂性越低。

计算机资源最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。

不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。

1．时间复杂性

【例4-1】设一程序段如下（为讨论方便，每行前加一行号）

（1）

（2）　　

（3）　　　　

试问在程序运行中各行执行的次数各为多少？

答：

可见，这段程序总的执行次数是：f（n）＝2n²＋2n＋1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果f（n）的值很小，则算法优。作为初学者，我们可以用f（n）的数量级O来粗略地判断算法的时间复杂性，如例4-1中的时间复杂性可粗略地表示为T（n）＝O（n²），即时间复杂度与n²呈线性关系。

对于不同数量级的n，在1s内我们有一些基本的时间复杂度，见表4.1。

表4.1　1秒内基本时间复杂度

2．空间复杂性

【例4-2】将一维数组的数据（n个）逆序存放到原数组中，下面是实现该问题的两种算法。

算法1：

算法2：

算法1的时间复杂度为2n，空间复杂度为2n；算法2的时间复杂度为3*n／2，空间复杂度为n＋1。

两个算法都实现了a数组的翻转，但显然算法2优于算法1，这两种算法的空间复杂度可粗略地表示为S（n）＝O（n），即空间复杂度与n呈线性关系。

在信息学比赛中，时间复杂度与空间复杂度往往不能共存。为了保证题目能在规定的时限（往往是1s）内出解，经常尽可能用空间换时间，即在不超内存的情况下，牺牲一些空间，以夺得时间的效率。