数据结构(1) - 简介

第一章 : 概念和复杂度

1. 数据结构含义

指描述一组数据时数据元素之间逻辑关系,数据在内存中存储的方式,和这组数据对外提供的标准操作api 的三个部分;

• (1) 数据的逻辑结构,分为四种: <1> 线性关系 <2> 树形关系 <3> 图形关系 <4> 集合关系
• (2) 数据的存储结构,分为两种: <1> 顺序存储 <2> 链式存储
• (3) 操作API : 主要分为三种类别, <1>添加 add()/put() <2> 删除 remove()/delete() <3> 查找 get()

2. 算法含义

3. 算法的时间复杂度

1. 含义:指某一算法,在计算过程中,源操作的执行次数

• 源操作:只程序计算过程中,嵌套最深的语句;
• 在java中,一个方法可作为单个的算法单元,即可以做复杂度分析,优化;

2. 一些经典数据结构本身的算法中时间复杂度计算举例

(1) linkedList 时间复杂度

• get(index) 其并没有直接维护索引,需要从两头查找(if (index < (size >> 1)) ... ...),需要遍历一半,所以时间复杂度是 O(n);
• add(Object) 默认添加到最后一个,固其复杂度是O(1);
• add(index,Object) 其过程是先执行和 get(index) 同样的逻辑,找到插入前的 索引为index 的元素,然后在其前面插入,需要遍历一半,所以时间复杂度是 O(n);
• remove() 默认移除第一个,时间复杂度是 O(1);
• remove(index) 需要执行 get(index) 同样的逻辑找到 该索引对应元素,时间复杂度是 0(n);
• 总结 : 涉及index时候,时间复杂度是O(n),否则是O(1).

(2) ArrayList 时间复杂度 :

• get(index) 维护了索引,直接索引指针指向查询时间复杂度是 O(1);
• add() 默认添加到末尾,复杂度是O(1);注意 : 此处需要与LinkedList区分,虽然都是O(1),但是原因是不一样的.一个是有索引维护指针,一个是用了linkLast()方法实现;
• add(index) 因为插入后需要维护index后面元素的索引( index=index+1),所以时间复杂度是 O(n);
• remove(index) 通 add(index) ,固为O(n);
• remove(Object) 需要遍历比对值,固为O(n);

参考文章 : https:www.cnblogs.com/zjss/p/5232048.html

(3) TreeMap 时间复杂度 :

• put(k,v) ,get(key),remove(key) 全是 O(log(n)).

因为treeMap 底层是红黑树,要对数据进行操作,首先要采用二分法的规则进行查找,这时候要找到某个key,最多需要运算的次数为log2(n),记为log(n)]

参考文章 : https:blog.csdn.net/li396864285/article/details/79820808

4. 算法的空间复杂度

1.含义

指一个算法运行开始到所占内存空间的大小

2.分类

主要由三个方面决定

• 算法本身占用空间
• 入参大小
• 临时辅助变量大小