考点精讲

1.1　算　法

【考点1】算法的基本概念

1．算法的定义

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

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

2．算法的基本特征

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

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

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

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

【真题演练】

算法的有穷性是指（　　）。[2013年9月真题]

A．算法程序的运行时间是有限的

B．算法程序所处理的数据量是有限的

C．算法程序的长度是有限的

D．算法只能被有限的用户使用

【答案】A

【解析】算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。答案选择A选项。

【考点2】算法设计基本方法

1．列举法

（1）基本思想

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

（2）特点

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

（3）使用

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

2．归纳法

（1）基本思想

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

（2）特点

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

（3）使用

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

3．递推

（1）基本思想

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

（2）特点

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

（3）使用

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

4．递归

（1）基本思想

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

（2）特点

结构清晰，可读性强。

（3）使用

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

（4）分类

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

（5）递归与递推的区别

a．递归是从算法本身到达递归的边界的；

b．递推是从初始条件出发，逐次推出所需求的结果。

5．减半递推技术

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

6．回溯法

（1）基本思想

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

（2）特点

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

【真题演练】

1下列叙述中正确的是（　　）。[2013年9月真题]

A．所谓算法就是计算方法

B．程序可以作为算法的一种描述方法

C．算法设计只需考虑得到计算结果

D．算法设计可以忽略算法的运算时间

【答案】B

【解析】A项错误，算法并不等同于计算方法，是指对解题方案的准确而完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情报；D项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。B项正确，程序可以作为算法的一种描述方法,算法在实现时需要用具体的程序设计语言描述。答案选择B选项。

2下列关于算法的描述中错误的是（　　）。[2014年3月真题]

A．算法强调动态的执行过程，不同于静态的计算公式

B．算法必须能在有限个步骤之后终止

C．算法设计必须考虑算法的复杂度

D．算法的优劣取决于运行算法程序的环境

【答案】D

【解析】算法是指对解题方案的准确而完整的描述。A项正确，算法强调实现，不同于数学上的计算方法；B项正确，算法的有穷性是指，算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成；C项正确，算法设计必须考虑执行算法所需要的资源，即时间复杂度与空间复杂度；D项错误，算法的优劣取决于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。答案选择D选项。

【考点3】算法复杂度

（1）时间复杂度

①定义

算法的时间复杂度是指执行算法所需要的计算工作量。

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

②在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：

a．平均性态

平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。

b．最坏情况复杂性

最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。

（2）空间复杂度

①定义

算法的空间复杂度一般是指执行这个算法所需要的内存空间。

②存储空间组成

a．算法程序占用的空间；

b．输入的初始数据占用的存储空间；

c．算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。

【真题演练】

1下列叙述中正确的是（　　）。[2015年3月真题]

A．算法的效率只与问题的规模有关，而与数据的存储结构无关

B．算法的时间复杂度是指执行算法所需要的计算工作量

C．数据的逻辑结构与存储结构是一一对应的

D．算法的时间复杂度与空间复杂度一定相关

【答案】B

【解析】采用不同的存储结构，数据处理效率是不同的，A项错误；算法的时间复杂度是指算法在计算机内执行时所需时间的度量，空间复杂度是指算法在计算机内执行时所需存储空间的度量，二者不一定相关，B项正确，D项错误；数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构，二者并非一一对应，C项错误。答案选择B选项。

2算法的空间复杂度是指（　　）。[2013年9月真题]

A．算法在执行过程中所需要的计算机存储空间

B．算法所处理的数据量

C．算法程序中的语句或指令条数

D．算法在执行过程中所需要的临时工作单元数

【答案】A

【解析】算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。包括算法程序所占空间，输入的初始数据所占空间和执行过程中所需要的额外空间。答案选择A选项。

3算法空间复杂度的度量方法是（　　）。[2014年9月真题]

A．算法程序的长度

B．算法所处理的数据量

C．执行算法所需要的工作单元

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

【答案】D

【解析】算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。包括算法程序所占空间，输入的初始数据所占空间和执行过程中所需要的额外空间。答案选择D选项。