导图社区 数据结构导图笔记
考研数据结构第一章的知识内容包括算法的基本概念、算法效率的度量，内容丰富全面且简单明了，有需要的朋友收藏下图学习吧！
社区模板帮助中心，点此进入>>
关于数据结构课程的一些问题
2021/8/21
1.2算法和算法评价
1.2.1算法的基本概念
为什么要引入算法
举例
比如累加求和的情况
1采用for循环
for(int i=0;i<=n;i++){sum+=i;}
那么此时算法需要进行循环的次数是和n的大小是有关系的
时间复杂度为:O(n)
2采用计算公式
sum=(1+n)/2
时间复杂度为:O(1)
总结
为了评价代码的性能(so 算法工程师的工资是要比程序员的高一些的)
数据结构的算法仅仅就是为了评价代码的性能
在考研中,递归分支贪心动态回溯分支限界这些都不需要去深入研究
算法的定义
特定为题的求解步骤
指令的有限序列
其中一个指令表示一个或者多个操作
算法的描述方法
自然语言(中文描述)
伪代码
最合适的一种算法
语言
C/C++/Java
伪
子主题
不陷入语言本身的细节问题
程序设计语法
指令
能被人或者计算机装置执行
你写的代码
5个特性
有穷性
有限步骤
每个步骤可以在有限时间内执行完
注意【易错点】：程序并没有又穷性的特点，一般情况下只要不去手动的进行关闭，那么程序就会一直运行在我们的CPU上
确定性
每一条指令都有确切的含义
相同的输入有确定的输出
可行性
都能在有限次后结束
输入
有0个或者多个
程序中可以没有输入
输出
有一个或者多个
形式是多样的
但是必须要有输出
助记
五行确穷输输
算法评价的4个反面
正确性
正确的层次
1算法程序没有语法错误
2对于合法的输入数据能够产生满足要求的输出结果
3对非法数据能够做出一定的处理,提示用户
4多于刁难的数据能够产生满足规格说明的结果
可读性
健壮性
对非法输入的数据能够进行相应的处理
高效率与低存储要求
效率
时间
时间短的算法效率高
存储量
空间
算法执行过程中需要的最大存储空间[主要是内存]
口诀
四剑确度笑脸
1.2.2算法效率的度量
分类
时间复杂度
空间复杂度
度量方法
事后统计法
复试需要上机写代码
ACM 牛客 剑指offer
定义
通过设计好的测试程序和数据
利用计算机计时器对不同算法编制的程序的运行时间进行比较
其中Java需要占用的内存和消耗时间是比较多的
缺陷
需要花费大量的精力去搞测试数据和程序
变量不单一 和计算机的硬件 编译器 运行框架都有影响
算法的测试数据设计困难
事前分析估算方法
在计算机编程前,依据统计方法对算法进行估算
关注点
抛开与计算机软硬件有关的因素
一个程序的运行时间,依赖于算法的好坏和问题的输入规模
所谓问题的输入规模就是指输入量的多少
eg:在累加求和中,n的值其实就是问题的输入规模
影响时间复杂度的有关因素
主题
