数据结构
所谓数据结构,首先明白研究对象是数据元素,而所谓数据元素可以理解为一条记录项,这是数据的解释.
结构指的是数据元素的关系.有逻辑关系,而逻辑关系指的是数据的结构的设计,实现则依赖于存储结构.
三要素
1. 逻辑结构
- 集合
- 线性结构:数据元素之间存在一对一关系
- 树形结构:数据元素之间存在一对多关系
- 图状结构或网状结构:数据元素存在多对多关系
2. 存储结构
- 顺序存储:逻辑上相邻物理位置上也相邻
- 链接存储:逻辑上相邻,物理位置不要求相邻
- 索引存储:存储元素信息时,建立附加的索引表.通过索引表去查找数据,而不是通过整个数据去查找信息
- 散列存储:根据元素的关键字直接计算该元素的存储地址(Hash存储)
3. 数据运算
常用的渐进时间复杂度
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
test
特别注意i=i*2这种 要看i初始值是不是2,是2的话,基本是logn的复杂度
void fun(int n)
{
int i=1;
while(i<=n)
i=i*2;
}
//算法复杂度:O(logn)
//i=1 while i=2
//i=2 while i=2^2
//i=3 whiel i=2^2^2
//...
//2^i <=n ==> i=logn