1.1　算　法

视频二维码（扫码观看）

一、算法的基本概念

1算法的定义

算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。

【注意】算法不等于程序，也不等于计算方法。

2算法的基本特征

（1）可行性（Effectiveness）：算法中的每一个步骤必须能够实现，执行的结果要能够达到预期的目的。

（2）确定性（Definiteness）：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释或多义性。

（3）有穷性（Finiteness）：算法必须能在有限的时间（合理的时间）内做完，即算法必须能在执行有限个步骤之后终止。

（4）拥有足够的情报：输入是否足够并正确，输出是否合理。初始状态是否正确。

二、算法设计基本方法

1列举法

（1）基本思想

根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

（2）特点

简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。

（3）使用

将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。

【例1】今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各几何？

假设买母鸡I只、公鸡J只、小鸡K只。根据题意，粗略的列举算法描述如下：

共有三层循环，每层循环各需要循环101次，大约为100万次。

优化后的算法

共有两层循环，循环次数为

2归纳法

（1）基本思想

通过列举少量的特殊情况，经过分析最后找出一般的关系。

（2）特点

归纳是一种抽象，即从特殊现象中找出一般关系。

（3）使用

由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。

3递推

（1）基本思想

从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。

（2）特点

本质上属于归纳法，递推关系式往往是归纳的结果。

（3）使用

递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。

4递归

（1）基本思想

为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。

（2）特点

结构清晰，可读性强。

（3）使用

递归在可计算性理论和算法设计中占有很重要的地位。

（4）分类

直接递归（自己调用自己）和间接递归（P调用Q，Q又调用P）。

【例2】编写一个过程，对于输入的参数n，依次打印输出自然数1到n。

非递归算法：

递归算法：

5减半递推技术

所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

【例3】设方程f（x）＝0在区间[a，b]上有实根，且f（a）与f（b）异号。利用二分法求该方程在区间[a，b]上的一个实根。

用二分法求方程实根的减半递推过程如下：

（1）首先取给定区间的中点c＝（a＋b）/2。

（2）然后判断f（c）是否为0：

如果f（c）＝0，则说明c即为所求的根，求解过程结束；

如果f（c）≠0，则根据以下原则将原区间减半：

①若f（a）f（c）＜0，则取原区间的前半部分；

②若f（b）f（c）＜0，则取原区间的后半部分。

（3）最后判断减半后的区间长度是否已经很小：

①若|a－b|＜ε，则过程结束，取（a＋b）/2为根的近似值；

②若|a－b|≥ε，则重复上述的减半过程。

6回溯法

（1）基本思想

通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。

（2）特点

在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。

三、算法复杂度

主要包括时间复杂度和空间复杂度。

1算法的时间复杂度

（1）定义

执行算法所需要的计算工作量。

（2）衡量标准

通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关。

综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量＝f（n）。

（3）存在问题

算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。

（4）解决方法

①平均性态（Average Behavior）

用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量：

②最坏情况复杂性（Worst-Case Complexity）

规模为n时，算法所执行的基本运算的最大次数：

2算法的空间复杂度

【定义】执行这个算法所需要的内存空间。

（1）算法程序所占的空间；

（2）输入的初始数据所占的存储空间；

（3）算法执行过程中所需要的额外空间。

【注意】

①如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。

②在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。

【考题1】算法的时间复杂度是指（　　）。

A．执行算法程序所需要的时间

B．算法程序的长度

C．算法执行过程中所需要的基本运算次数

D．算法执行过程中所需要的所有运算次数

E．算法程序中的指令条数

【答案】C

【解析】算法的时间复杂度是指算法执行过程中所需要的基本运算次数。执行算法程序所需要的时间、算法长度、指令条数等与时间复杂度没有直接关系。

【考题2】算法的空间复杂度是指（　　）。

A．算法程序的长度

B．算法程序中的指令条数

C．算法程序所占的存储空间

D．算法执行过程中所需要的存储空间

E．算法所处理的数据量

【答案】D

【解析】算法的空间复杂度是指算法执行过程中所需要的存储空间。算法程序的长度、指令条数、所处理的数据量等与空间复杂度没有直接关系。