1.1 数据结构与算法

考点1 算法

真考链接

在选择题中，考核概率为45%。该知识点属于熟记内容，应熟记算法、时间复杂度和空间复杂度的概念。

1.算法的基本概念

算法是指解题方案的准确而完整的描述。

（1）算法的基本特征

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

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

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

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

（2）算法的基本要素

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

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

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

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

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

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

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

2.算法复杂度

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

（1）算法的时间复杂度

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

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

算法的工作量=f（n）

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

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

（2）算法的空间复杂度

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

●算法程序所占的空间；

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

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

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