数据结构（1）

数据结构其实就是将数据按照一定的关系组织起来的集合，用于组织和存储数据。

1.数据结构分类

1.逻辑结构

        逻辑结构是从具体问题中抽象出来的模型，是抽象意义的结构，按照对象中数据的相互关系进行分类。

        1>集合结构：集合结构中的元素除了属于同一个集合外，他们之间没有任何联系。

        2>线性结构：线性结构中的元素之间存在一对一的关系。

        3>树形结构：树形结构中的元素存在一对多的层级关系。

        4>图形结构：图形结构中的元素是多对多的关系。

2.物理结构

        逻辑结构在计算机中真正的表达方式，也称为存储结构。

        1>顺序存储结构：将数据放到地址连续的存储单元里面，数据间的逻辑关系和物理关系是一致的。

        2>链式存储结构：将数据存放在任意的存储单元中，存储单元可以连续也可以不连续，数据之间的逻辑关系不能反映物理关系，因此引入了一个指针存放数据的地址，通过指针找到相关数据间的位置。

2.算法

为了解决问题，对数据进行计算，得到需要的结果。

1.函数渐进增长

1.算法函数中的常数可以忽略

2.算法函数的最高次幂的常数因子可以忽略

3.算法函数最高次幂越小，算法效率越高

2.大O计数 时间复杂度

常数级别: 1 普通语句 将两个数相加
对数级别: logN 二分策略 二分查找
线性级别: N 循环 找出最大元素
线型对数级别: NlogN 分治思想 归并排序
平方级别: N^2 双层循环 检查所有元素对
立方级别: N^3 三层循环 检查所有三元组
指数级别: 2^N 穷举查找 检查所有子集

复杂层度：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)

3.空间复杂度

数据类型 内存占用字节数
byte 1
short 2
int 4
long 8
float 4
double 8
boolean 1
char 2