考研 数据结构(考研数据结构参考)




考研 数据结构,考研数据结构真题

今天为大家带来的是《数据结构》必会的核心考点,接下来的每一天,学长都会更新计算机考研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)。

考研 数据结构(考研数据结构参考)

未经允许不得转载:北京考研网 » 考研 数据结构(考研数据结构参考)

赞 (0) 打赏

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏