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