硬核干货 | 数据结构必会核心考点（一）

今天为大家带来的是《数据结构》必会的核心考点，接下来的每一天，学长都会更新计算机考研408的四个科目的核心考点，帮助考24研的同学快速理清科目重点知识点，树立学科知识框架。

考点1：时间复杂度与空间复杂度

➤【考点笔记】时间复杂度

时间复杂度T(n)是指算法中所有语句的频度(执行次数)之和。人们关心的是当n趋于无穷时T(n)的数量级，而非T(n)的准确大小，因此以T(n)的数量级来表征时间复杂度。

例如，T(n)=n3+n2+n，可认为时间复杂度T(n)=O(n3)，这里数量级最大的一项必定是由最深层循环的语句贡献的，称之为基本运算。由于T(n)与算法中基本运算的频度f(n)同数量级，所以通常采用基本运算的频度的数量级O(f(n))来分析算法的时间复杂度，记为T(n)=O(f(n))。

最终归结为一句话：将算法中基本运算的执行次数的数量级作为时间复杂度。

时间复杂度的计算遵循两种规则：

· 加法法则：

T(n)=T1(n)+Tn(n)=O(f(n))+O(g(n))=O(max(f(n)，g(n)))

· 乘法法则：

T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))

例如，设a{ }、b{ }、c{ }三个语句块的时间复杂度分别为O(1)、O(n)、O(n2)，则

1) a{

b{ }

c{ }

}的时间复杂度为O(n2)，满足加法法则；

2) a{

b{

c{ }

}的时间复杂度为O(n3)，满足乘法法则。

注意：有些情况下，算法中基本运算的执行次数还随问题的输入数据集的不同而不同。

➤ 【考点拓展】递归算法

递归是算法领域的一个重要思想。在后续的二叉树中也有递归的应用。递归算法可以通过迭代或栈改写为非递归算法。以本题为例，也可写成以下两种方式：

递归算法的特性：

①一个算法直接或间接调用自身。

②必须有一个明确的递归结束条件，称为递归出口。

由于递归算法需要反复进行函数调用与返回，运行效率较低。实现递归的关键是建立递归调用工作栈。当有多个函数构成嵌套调用时，按照后调用先返回的原则，因此递归调用需要开辟栈以存放每一层的返回点、局部变量等，栈的大小也就是递归深度和递归算法空间复杂度的大小。

➤ 【考点笔记】空间复杂度

空间复杂度S(n)指算法运行过程中所使用的辅助空间的大小，通常结合算法题考查。

若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入数据和程序之外的临时分配的额外空间。算法原地工作是指算法所需辅助空间是常量，即O(1)。

考点2：线性表的顺序表示

➤【考点笔记】时间复杂度

顺序表是指用一组连续的存储单元，依次存储线性表中的各个元素，从而使得逻辑上相邻的元素在物理位置上也相邻，因此可以随机存取(根据首元素地址和元素序号)表中任一元素。

顺序表的缺点也很明显，如元素的插入和删除需要移动大量的元素，插入操作平均需要移动n/2个元素，删除操作平均需要移动(n-1)/2个元素，而且存储分配需要一段连续的存储空问，不够灵活。

➤ 【考点笔记】顺序表的插入操作

对于插入算法，若表长为n，则在第f位置插入元素，则从an到ai都要向后移动一个位置，共需移动n-f+1个元素，平均时间复杂度为O(n)。代码片段如下：

➤ 【考点笔记】顺序表的删除操作

对于删除算法，若表长为n，当删除第i个元素时，从ai+1到an都要向前移动一个位置，则共需移动n-i个元素，平均时间复杂度为O(n)。代码片段如下：

➤ 【考点笔记】顺序表的查找

(1)按序号查找，顺序表具有随机存取(根据首元地址和序号)的特点，时间复杂度为O(1)。

(2)按值x查找，主要运算是比较操作，比较的次数与值x在表中的位置有关，也与表长有关，平均比较次数为(n+1)/2，时间复杂度为O(n)。