关系的映象 两种根本方法及其组合使用。 顺序映象:以相对的存储位置表示关系 链式映象:以附加信息(指针)表示关系 注意:数据的逻辑构造和存储构造的关系 可以用数组等线形存储的方式存储逻辑上的树形构造 也可以用树状的复杂的存储构造来存储逻辑上的集合关系以到达提高
检索速度的目的
数据的逻辑结构与存储结构
正确性〔最重要的标准〕 算法应满足具体问题的需求 对于典型的、苛刻而带有刁难性的一组有效输入得到
正确的结果 强健性 算法应具有容错处理。当输入非法数据时,算法应对
其作出反响,而不是产生莫名其妙或随机的输出结果 可读性 算法应该好读。以有利于阅读者对程序的理解和维护 高效性:时间复杂度 算法执行占用的CPU时间,随问题规模n的变化函数 高效性:空间复杂度 算法执行占用的内存总量,随问题规模n的变化函数
a1 a2 a3 … ai … an
根本术语
数据 被计算机加工处理的对象。 数据元素〔记录、表目〕 数据的根本单位,
是数据集合中的一个有意义的个体。 数据项 一个数据元素可由假设干个数据项组成。
பைடு நூலகம்
学 号姓 名班 号性别出生日期入学成绩
原子项
年月日
组合项
根本术语2
数据对象 是性质一样的数据元素的集合,是 数据的一个子集。
学号 姓名 班号 性别 出生日期 数据入元学素 成绩
增长率一样
时间复杂度曲线
常见的时间复杂度:
O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n)
O(1)<O(log2n)<O(n)< O(nlog2n)<(n2)<O(n3) <<O(2n)
空间复杂度
算法所需存储空间的度量