数据： 对客观事物的符号表示，之所有能输入到计算机中并被计算机程序处理的符号的总称
数据元素：数据的基本单位
可由若干个数据项组成
数据项：数据的不可分割的最小单位
数据对象：性质相同的数据元素的集合，是数据的一个子集
数据结构：
定义：相互之间存在一种或多种特定关系的数据元素的集合
表示：Data Structure=<D,S>，D是数据元素的有限集，S是D上关系的有限集
分类：
① 逻辑结构：结构定义中的“关系”描述的是数据元素之间的逻辑关系，故称为数据的逻辑结构
② 物理结构：数据结构在计算机中的表示（映像）
a.顺序映像：顺序存储结构
b.非顺序映像：链式存储结构
抽象数据类型：指一个数学模型以及定义在该模型上的一组操作
三元组表示：<D,S,P>
D是数据对象
S是D上的关系集
P是对D的基本操作集
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
算法：对特定问题求解步骤的一种描述
算法的特性*：
① *有穷性 一个算法必须总是在执行有穷步骤后结束，且每步都可在有穷时间内完成
② 确定性 算法中每条指令必须有确切的含义，不允许二义性
③ 可行性 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现
④ 输入 零个或多个输入
⑤ 输出 一个或多个输出
算法设计的要求:
① 正确性 算法应满足设定的功能和要求
② 可读性 思路清晰、层次分明、易读易懂
③ 健壮性 输入非法数据时能作适当的反映和处理
④ 效率与低存储需求 完成同一功能，执行时间短，效率高，占用存储空间少
算法效率的度量
事后统计的方法：
缺陷：①必须先运行依据算法编制的程序
②所得时间的统计量依赖于计算机的硬件、软件等环境因素
事前分析估算方法：
取决因素：①依据算法选用何种策略
②问题的规模
③书写程序的语言，实现的语言级别越高，效率越低
④编译程序所产生的机器代码的质量
⑤机器执行指令的速度
a.同一算法用不同语言实现，或者用不同编译程序编译，或在不同计算机上运行，效率不同。
b.撇开与计算机硬件、软件的因素，算法的“运行工作量”大小只依赖于问题的规模（通常用证数量n表示）
算法的时间复杂度:
a.一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果
b.方便起见，从算法中选取一种对于所研究问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行次数作为算法的时间度量
c.频度：该语句重复执行的次数
d.T(n)=O(f(n))——随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称为算法的渐近时间复杂度，即时间复杂度
算法的空间复杂度:
a.一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算机所需信息的辅助控件
b.若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外控件，否则应同时考虑输入本身所需控件
c.若额外控件相对于输入数据量来说是常数，则称此算法为原地工作
d.S(n)=O(f(n))
