是信息的载体
是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
一个数据元素可由若干数据组成,数据项是构成数据元素的不可分割的最小单位
数据元素是数据的基本单位,通常作为一个整体进行考虑和处理
具有相同性质的数据元素的集合,是数据的一个子集
是相互之间存在一种或多种特定关系的数据元素的集合
同一个数据对象里的数据元素,可以组成不同的数据结构
不同的数据元素,可以组成相同的数据结构
值的范围:true、false
可进行操作:与、或、非
值的范围:-2147483648 ~ 2147483647
可进⾏操作:加、减、乘、除、模运算
struct结构体
是抽象数据组织及与之相关的操作
定义一个ADT,就是在“定义”一种数据结构
一般线性表
栈
队列
串
数组
各个元素同属一个集合,别无其他关系
一般树
二叉树
有向图
无向图
结合逻辑结构、实际需求来定义基本运算
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
链式存储
索引存储
散列存储
非顺序存储
数据结构是要处理的信息
算法是处理信息的步骤
用有限步骤解决某个特定的问题
如:微信是程序,不是算法
相同输入只会产生相同输出
可以用已有的基本操作实现算法
一个算法有零个或多个输入
丢给算法处理的结果
一个算法有一个或多个输出
算法处理的结果
能正确解决问题
对算法的描述要让其他人也得看懂
算法能处理一些异常状况
即算法执行省时、省内存
时间复杂度低、空间复杂度低
1.找到一个基本操作(最深层循环)
2.分析该基本操作的执行次数x与问题规模n的关系x=f(n)
3.x的数量级O(x)就是算法时间复杂度T(n)
多项相加,只保留最高阶的项,且系数变为1
多项相乘都保留
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²)
最坏情况下算法的时间复杂度
所有输入示例等概率出现的情况下,算法的期望运行时间
最好情况下算法的时间复杂度
1.找到所占空间大小与问题规模相关的变量
2.分析所占空间x与问题规模n的关系x=f(n)
3.x的数量级O(n)就是算法空间的复杂度
1.找到递归调用的深度x与问题规模n的关系x=f(n)
2.x的数量级O(n)就是算法空间复杂度S(n)
空间复杂度 = 递归调用的深度
T(n) = T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
T(n) = T₁(n)×T₂(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²)