数据的逻辑结构
-
逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。
-
集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。
-
线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f- g·····被一根线穿连起来。
-
树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。
-
图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。
-
数据的存储(物理)结构
-
存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。
-
顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。
-
链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。
-
小结:数据的逻辑结构和物理结构是密切相关的,在学习数据的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构。
算法
有穷性、可行性、确定性、输入、输出
时间复杂度
- 语句频度:该条语句可能重复执行的次数
- T(n):所有语句的频度之和,其中n为问题的规模
- 时间复杂度:T(n)=O(f(n)),其中O表示T(n)与f(n)在n->正无穷时为同阶无穷大
规则:
- 加法规则
- 乘法规则
常见时间复杂度
$O(1)$<$O(log_2n)$<$O(n)$<$O(nlog_2n)$<$O(n2)$<$O(n3)$<$O(2n)$<$O(n!)$<$O(nn)$