1.算法的时间与空间复杂度定义

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。

空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

一、时间复杂度

常见的时间复杂度量级有：

常数阶O(1)

对数阶O(logN)

线性阶O(n)

线性对数阶O(nlogN)

平方阶O(n²)

立方阶O(n³)

K次方阶O(n^k)

指数阶(2^n)

二、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)

---

2.线性表

线性表之顺序表

应用：    ArrayList 源码实现功能用arraycopy
•优点：

     尾插效率高，支持随机访问。

•缺点：

     中间插入或者删除效率低。

线性表之链表

定义：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的

数据元素，这组存储单元可以是连续的，也可以是不连续的

1、单循环链表

应用：HashMayEntry

顺序表 ArrayList

优点：存储空间连续允许随机访问 尾插，尾删方便

缺点：插入效率低删除效率低长度固定

单链表

优点： 随意进行增删改，插入效率高删除效率高，长度可以随意修改

缺点： 内存不连续，不能随机查找

双链表LinkedList

优点：随意进行增删改,插入效率高,删除效率高长度可以随意修改,查找效率比单链表快一倍

缺点:内存不连续,不能随机查找，但是效率比单链表快一倍

2、双向循环链表

应用:LinkList