1.1 数据结构与算法

考点1 算法

1.算法的基本概念

算法是指一系列解决问题的清晰指令。

（1）算法的基本特征。

●可行性：针对实际问题而设计的算法，执行后能够得到满意的结果，即必须有一个或多个输出，即使在数学理论上是正确的，如果在实际的计算工具上不能执行，则该算法也是不具有可行性的。

●确定性：是指算法中每一步骤都必须是有明确定义的。

●有穷性：是指算法必须能在有限的时间内做完。

●拥有足够的信息：一个算法是否有效，还取决于为算法所提供的信息是否足够。

（2）算法的基本要素。

算法一般由两种基本要素构成：

●对数据对象的运算和操作；

●算法的控制结构，即运算和操作时间的顺序。

算法中对数据的运算和操作：算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统，指令系统是有差异的，但一般的计算机系统中包括的运算和操作有4类：算术运算、逻辑运算、关系运算和数据传输。

算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅取决于所选用的操作，还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构。

（3）算法设计的基本方法。

算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。

2.算法复杂度

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

（1）算法的时间复杂度。

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

一般情况下，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量=f（n）

其中n表示问题的规模。该表达式表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。

在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用两种方法来分析算法的工作量：平均性态分析和最坏情况分析。

（2）算法的空间复杂度。

算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括以下3个部分：

●算法程序所占的空间；

●输入的初始数据所占的存储空间；

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

在实际操作中，为了减少算法所占的存储空间，通常采用压缩存储的技术，用于减少不必要的额外空间。

真考链接

考核概率为45%。考生要熟记该考点的内容，尤其是算法的概念，以及时间复杂度和空间复杂度的概念。