2022考研数据结构实战攻略：教材缺陷下的冲刺指南
需积分: 48 113 浏览量
更新于2024-07-15
7
收藏 5.43MB PDF 举报
"《22考研数据结构复习全书》是由灰灰考研团队编著的一本专为准备考研的数据结构学习资料。该书旨在帮助考生突破传统教材的局限，弥补现有考研教材在实战能力培养上的不足。作者团队以华中科技大学和武汉大学等名校学生的考研经验为基础，充分理解考研学生的不易，强调基础知识与实际应用的结合。
本书的特点在于其实战导向，编者投入大量精力设计章节布局，精心挑选和解析考题，以确保内容既全面覆盖考试大纲，又包含历年名校真题中的精华。不同于市面上常见的教材，它避免了题目的冗余解释和粗略讲解，而是提供适量且深入的题目分析，有助于考生提升解题技巧和实战应对能力。
《22考研数据结构复习全书》是灰灰考研复习全书系列的一部分，包括了《数据结构》、《计算机网络》、《操作系统》、《计算机组成原理》等多个领域，还配套有习题册，以加深理解和巩固所学知识。这套图书以408统考大纲为基准，确保内容的权威性和实用性，旨在帮助考生在备考过程中提高效率，更好地应对考研挑战。
对于准备考研的数据结构部分，本书是一份宝贵的参考资料，它不仅提供理论知识，更注重培养考生将理论知识转化为实际解题能力的能力，是考研路上不可或缺的支持。对于有志于计算机科学专业考研的学生来说，这本书是他们在知识积累和技能提升道路上的重要里程碑。"
数据结构考研攻略
8
1.2.3 时间复杂度专题讲解
大 O 表示法：称一个函数 g(n)是 O(f(n))，当且仅当存在常数 c>0 和 n0>=1，对一切 n>n0
均有|g(n)|<=c|f(n)|成立，也称函数 g(n)以 f(n)为界或者称 g(n)受限于 f(n)。记作 g(n)=O(f(n))。
定义：如果一个问题的规模是 n，解这一问题的某一算法所需要的时间为 T(n)，它是 n
的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量 n 逐渐加大时，时间复杂度的
极限情形称为算法的“渐近时间复杂度”。
下面给出常见的时间复杂度的题型的解决办法：
①循环主体中的变量参与循环条件的判断
例 1： int i=1;
while(i<=n)
i =i*2;
解题思路：
假设程序执行了 k 次，那么意味着 i 乘以 2 的次数也为 k，于是有：2
k
≤n,那么 k≤log
2
n,即时
间复杂度为 T(n)=O(log
2
n)
例 2：（ 2017 华中科技大学 834）如下程序段的时间复杂度为( )。
void main(){
int s=0,i=0;
do{
i=i+1;
s=s+i;
}while( i<=n);
};
A. O(nlogn) B.O(n) C.O(n ^2) D.(n ^3/2)
解题思路：
a）确定参与循环的变量：i
b）在本程序段中，虽然给出了两个变量 i 和 s，但是最终循环结束的条件是 i≤n，与 s 无关，
i 每次自加 1
c）得出程序片段的时间复杂度为：B. O(n)
②循环主体中的变量不参与循环条件判断
Situation 1:递归程序（主要考察点）
分治法主定理： T [n] = aT[n/b] + f (n)
其中 n 为问题规模 a ≥ 1 and b > 1 是常量 并且 f (n) 是一个渐近正函数，也就
是递归以外的计算时间，为了使用这个主定理，需要考虑下列三种情况：
Case1：如果
)()(f
log
a
b
nOn
对于某个常量ε>0 成立，那么 T（n）=O(
a
b
log
n
)
Case2:如果
)()(f
log a
b
nOn
，那么 T（n）=O(
a
b
log
n
logn)
Case3:如果
)()(f
log
a
b
nOn
对于某个常量ε>0 成立，并且 af(n/b)≤cf(n)
对于某个常量 c<1(n 足够大)成立，那么 T（n）=O(
f(n)
)
剩余134页未读，继续阅读
2021-12-05 上传
2021-09-30 上传
2018-04-18 上传
2023-10-10 上传
2020-01-02 上传
2023-09-19 上传
灰灰考研
- 粉丝: 91
- 资源: 25
我的内容管理
展开
最新资源
- 新型智能电加热器：触摸感应与自动温控技术
- 社区物流信息管理系统的毕业设计实现
- VB门诊管理系统设计与实现(附论文与源代码)
- 剪叉式高空作业平台稳定性研究与创新设计
- DAMA CDGA考试必备：真题模拟及章节重点解析
- TaskExplorer：全新升级的系统监控与任务管理工具
- 新型碎纸机进纸间隙调整技术解析
- 有腿移动机器人动作教学与技术存储介质的研究
- 基于遗传算法优化的RBF神经网络分析工具
- Visual Basic入门教程完整版PDF下载
- 海洋岸滩保洁与垃圾清运服务招标文件公示
- 触摸屏测量仪器与粘度测定方法
- PSO多目标优化问题求解代码详解
- 有机硅组合物及差异剥离纸或膜技术分析
- Win10快速关机技巧：去除关机阻止功能
- 创新打印机设计：速释打印头与压纸辊安装拆卸便捷性
