数据结构第一章
2021-11-13 15:39:48 10 举报AI智能生成
登录查看完整内容
为你推荐
查看更多
数据结构第一章的网课笔记
作者其他创作
大纲/内容
数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科
概念
数值型
非数值型
数据
数据的基本单位
数据元素
最小单位
数据项
性质相同的数据元素的集合
数据对象
集合、线性、树状、图状
逻辑结构
顺序、链式、索引、散列
储存结构
运算与实现（操作）
数据结构
性质相同的值的集合与在这集合上的一组操作
数据类型
各个数据对象之间的逻辑关系
这些数据对象上的操作
抽象数据类型
基本概念和术语
指令的有限序列
定义
自然语言
流程图
代码
伪代码
描述
确定性
可行性
有穷性
零个或多个
输入
一个或多个
输出
特性
不含语法错误
对于几组输入的数据能够得到预期结果
对于苛刻的数据也能得到正确结果
一切对合法的输入都能得到正确结果
正确性
可读性
输入非法数据时能够返回合理的提示
处理出错时能够返回关于错误的提示而不是终止程序运行
健壮性
高效性
要求
算法
事后统计
算法运行时间=一次操作时间×操作次数
基本语句：执行次数最多的语句
定义：基本语句执行的次数是问题规模n的某个函数f(n)
如：T(n)=O(n²)
找基本语句
计算由基本语句得到的问题规模n的某个函数f(n)
取其数量级
找最高次幂的那一项，忽略所有低次幂项与最高次幂项的系数
计算方法
最好、最坏、平均时间复杂度
时间复杂度的渐进表示法：O（f（n）），简称：时间复杂度
事前分析
时间效率
本身所需的空间：指令、常数、变量等
辅助空间
算法要占据的空间
S(n)=O(1)：原地工作
例题
渐进空间复杂度：S(n)=O(f(n))
空间效率
算法效率
总结
算法分析
算法和算法分析
数据结构第一章
0 条评论
回复 删除
下一页
