数据(data):信息的载体,能够被计算机识别、存储和加工处理。包括数值型数据和非数值型数据。
数据元素(data element):数据的基本单位。
数据项(data item):构成数据元素的不可分割的最小单位。也称为字段或者域。
数据类型(data type):具相同性质的计算机数据的集合以及在这个数据集合上的一组操作。分为简单(原子)类型、构造(结构)类型和抽象数据类型。
抽象数据类型(abstract data type,ADT):一个数学模型及定义在该模型上的一组操作。抽象的意义在于数据类型的数学抽象特性。ADT体现了程序设计中问题分解、抽象和信息隐藏的特性。
数据结构(data structure):按照某种逻辑关系组织起来的一组数据,按一定的存储方式在计算机的存储器中,并在这些数据上定义了一组运算的集合。数据结构三要素:逻辑结构、存储结构(物理结构)、数据的操作和运算。
常见逻辑结构:集合、线性结构、树结构、图结构。
基本存储结构:
顺序存储:用一组连续的存储单元依次存储各个数据元素。
链式存储:用任意存储单位储存各个数据元素,数据元素之间的关系用指针表示。
索引存储:建立附加索引表。
散列存储(哈希存储):使用关键字计算出存储地址。
数据的存储结构影响存储空间分配的方便程度和数据运算的速度。
算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
算法的5个准则:
1.输入:具有0个或者多个输入的参数。
2.输出:算法执行要有输出的结果。
3.有穷性:执行又穷步之后能够结束。
4.确定性:每条指令必须有确切的意义,无二义性。
5.可行性:每条指令的运算时间是有限的。
优秀算法的特质:
正确性、可读性、健壮性、高效率(时间复杂度低)、低存储要求(空间复杂度低)。
时间复杂度:事前预估算法时间开销T和问题规模n的关系。关注最坏情况和平均情况。
空间复杂度:空间开销S和问题规模n之间的关系。
只考虑阶数最高的部分。(常对幂指阶)