数据结构(1)序章
数据结构序章
数据元素的相关基本概念
数据结构主要研究数据元素之间的关系。
数据结构三要素
逻辑结构(定义一种数据结构)
既然数据结构是研究数据元素之间的基本关系,那基本关系如何表示呢?逻辑结构就是根据数据元素之间关系的不同特性,分为了4类基本结构
- 集合
- 线性结构
- 树形结构
- 图状结构
数据的运算
定义好了逻辑结构,我们能进行什么操作呢?数据的运算就是结合逻辑结构以及实际需求来定义的基本运算,举个栗子?,我们定义一个线性表的结构,可以进行的数据运算有查找,增加,删除等等
物理结构(在计算机中实现)
我们定义好了逻辑结构,又想好了该需要有哪些运算,那如何在计算机中实现呢?那这里给出四种基本方法
- 顺序存储
- 链式存储
- 索引存储
- 散列存储
其中后三者都是非顺序存储的。以上:逻辑结构,数据的运算以及物理结构就是数据结构的三要素
数据类型和抽象数据类型
数据类型
先挑熟悉的说:数据类型。相信在学习C语法的时候我们对数据类型已经很熟悉了,常用的int型,float型,char型都是数据类型。这里我们给出一个通俗的定义,我们只关注其中两个东西,即这个数据类型的值的范围以及可进行的操作。还是举个栗子?,就拿bool型来说,值的范围是0,1,可进行的操作是:与、或、非等基本逻辑运算。
抽象数据类型(ADT)
看完数据类型,抽象数据类型也很容易理解了,还是先给出一个不太通俗的定义:抽象数据类型是 抽象数据组织 以及 与之相关的操作。通俗点讲就是站在使用者的角度,我只需要知道这个数据元素之间是什么结构关系,以及可以执行什么操作。
算法序章
我们知道,程序 = 数据结构 + 算法。在上面提到,数据结构是如何用数据描述现实世界,然后存进计算机,那么算法通俗点讲就是:如何处理这些数据来解决问题。
算法的5个特性(缺一不可)
- 有穷性
- 确定性
- 每条指令有确定含义
- 相同输入必须得出相同输出
- 可行性
- 输入
- 输出
有了上面5个特性,我们才可以说它是一个算法。那么从一个算法进化到一个好的算法又需要什么呢?
- 正确性
- 可读性:语言能看懂 , 注释
- 健壮性 :考虑到一些边界条件和非法数据
- 效率与低存储量需要(时空复杂度)
空间复杂度
空间复杂度,顾名思义,就是这个程序运行时需要的内存需求,想知道它需要多少内存,我们应该先知道,一个程序在运行时,哪些东西需要占用内存。那么无非就是两个东西,即:
- 这个程序代码占用的内存,这一部分的大小是固定的,因此不在空间复杂度的研究范围内
- 数据占用的内存:即变量以及参数等等
所以对于非递归程序,找到和所占空间大小相关的变量分析即可
递归程序
对于递归程序,因为每次调用一遍递归函数都要占用新的空间,所以在分析递归程序的空间复杂度时,要找到递归调用的深度和问题规模n的关系。调用深度x的数量级就是空间复杂度
时间复杂度
事后统计的问题
- 和运行机器的性能有关
- 和编程语言有关,越高级的语言执行效率越低
- 有的算法不能事后统计:导弹控制算法
- 和编译程序产生的机器指令质量有关
一言概之,受太多外界因素的影响
事前分析
- 可以只考虑阶数高的部分
- 加法规则:多项相加,只保留最高阶的项,且系数变为1
- 乘法规则:多项相乘,都保留
- 数量级口诀:常对幂指阶
如果有好几千行代码,需要一行一行数吗?
- 顺序执行的代码只会影响常数项,可以忽略
- 只需在循环操作中挑一个语句分析它的执行次数 i 与 n 的关系即可,(列出等式判断)
- 如果有多层嵌套循环,只关注最内层循环即可
三种复杂度
- 最坏时间复杂度:输入数据最坏的情况
- 最好时间复杂度
- 平均时间复杂度:输入数据等概率出现
一般只考虑算法的最坏时间复杂度和平均时间复杂度。
相关文章
- Java核心知识体系3:异常机制详解
- Java核心知识体系2:注解机制详解
- Java核心知识1:泛型机制详解
- Java:导出Excel大批量数据的优化过程
- Springboot返回数据null转空字符串
- java记录项目的UV值与PV值
- 小米手机自拍图标-小米Civi 1S体验:这次,男生也能自拍美颜了
- java文件网络路径转MultipartFile
- 百度短信接口以及人脸实名认证接口
- 怎样使用摄像机-索尼高清摄像机使用方法简要介绍【教程】
- 小米手机自拍图标-小米Civi 1S vs 小米9:最强自拍手机的后置镜头咋样?
- spring框架
- hexo博客插入音视频
- java实用小功能案例
- Excel自动化办公
- Open-CV图像处理
- open-CV的初步学习
- 树莓派 usb-使用您的树莓派
- NLP和知识图谱-neo4j安装和使用
- adobe cs6 系列软件通用破解补丁-Adobe CC全系列注册机-Adobe CC通用破解补丁1.1 中文免费版