博客

算法复杂度：分为

时间复杂度

和

空间复杂度

。

前言：经常出现问集合，比如问ArrayList，其get(int index)方法,add(E e)方法，add(int index, Eelement)方法，remove(int index)方法，时间复杂度分别是多少？再比如问LinkedList，其get(int index)方法,add(E e)方法，add(int index, E element)方法，remove(int index)方法，时间复杂度分别是多少？

看过我上2个文章写的

Java中数据结构

、

Java中集合

文章的小伙伴就会知道，ArrayList和LinkedList的区别，是这两个集合的底层数据结构不一样。前者底层数据结构是

数组

，后者底层数据结构是

双向循环链表

。所以，这两个集合的查找、增、删等方法，效率不一样，也就是时间复杂度不一样。【记得请看我另外两个文章】

一. 算法复杂度含义：

• 
  时间复杂度
  
  是度量算法执行时间的长短；同时也是一个函数，它定量描述了该算法的运行时间。
• 
  空间复杂度
  
  是指算法所需存储空间的大小。
  
  (所以针对集合的查询方法，经常会问时间复杂度是多少这些问题。)

二. 举例：

1. 举例时间复杂度：
   
   用通俗的话来描述，我们假设n=1所需的时间为1秒。那么当n=10000时。
   
   O（1）的算法需要1秒执行完毕。
   
   O（n）的算法需要10000秒 ≈ 2.7小时 执行完毕。
   
   O（n2）的算法需要100000000秒 ≈ 3.17年 执行完毕。
   
   O（n！）的算法需要XXXXXXXX(系统的计算器已经算不出来了)。
   
   可见算法的
   
   时间复杂度
   
   影响有多大。
   
   所以例子中的O（1）和O（n）差了2.7小时，区别显而易见。
2. 时间复杂度，O(1)和O(n)区别：
   
   O(1)复杂度是与输入数据无关，O(n)是与输入数据成正比。
   
   对于程序A，for(int i=0;i<1000;i++)，当输入任意的n时循环次数均为1000，复杂度为O(1)；
   
   对于程序B，for(int i=0;i<n;i++)，当输入任意的n时循环次数为n，复杂度为O(n)。
3. 空间复杂度，略~~~~~~

三.常见集合，其方法的时间复杂度

1. ArrayList各方法的时间复杂度：
   
   【底层是数组，查询方法效率高】
   
   
   
   get(int index)方法
   
   获取指定索引位置的元素，时间复杂度为O(1)。
   
   
   add(E e)方法
   
   添加元素到末尾，平均时间复杂度为O(1)。
   
   add(int index, E element)方法
   
   添加元素到指定位置，平均时间复杂度为O(n)。
   
   remove(int index)方法
   
   删除指定索引位置的元素，时间复杂度为O(n)。
   
   remove(Object o)方法
   
   删除指定元素值的元素，时间复杂度为O(n)。
2. LinkedList各方法的时间复杂度：
   
   【底层是链表，增删方法效率高】
   
   
   get(int index)方法
   
   获取指定索引位置的元素，时间复杂度为O(n)。
   
   
   add(E e)方法
   
   添加元素到末尾，平均时间复杂度为O(1)。
   
   
   add(int index, E element)方法
   
   添加元素到指定位置，平均时间复杂度为O(n)。
   
   
   remove(int index)方法
   
   删除指定索引位置的元素，时间复杂度为O(1)。
   
   remove(Object o)方法
   
   删除指定元素值的元素，时间复杂度为O(1)。
   

四.

详解

常见集合，其方法的时间复杂度

• Arraylist：底层数据结构是动态数组，
  
  根据下标随机访问数组元素的效率高，向数组尾部添加元素的效率高；
  
  但是，向数组中
  
  指定位置添加数据
  
  以及
  
  删除数组中的数据
  
  效率低，因为需要移动数组，会进行大量的数组移动复制操作,而数组复制时，最终将调用System.arraycopy()方法。(delete方法，例如最坏的情况是删除第一个数组元素，则需要将第2至第n个数组元素各向前移动一位。)
  
  而之所以称为动态数组，是因为Arraylist在数组元素超过其容量后,Arraylist可以进行扩容（针对JDK1.8， 数组扩容后的容量是扩容前的1.5倍）。
• Linkedlist：底层数据结构是双向链表(JDK1.7 之后取消了循环)，
  
  数据添加删除效率高，只需要改变指针指向即可;
  
  但是访问数据的效率低，需要对链表进行遍历。
  
  Linkedlist集合，每次插入add()都是移动指针，和 ArrayList 的拷贝移动数组 来说效率要高上不少。

五.总结

• ArrayList查询,修改都根据索引效率高.因为LinkedList要移动指针。
• LinkedList插入,删除都是移动指针效率很高.因为ArrayList要复制移动数据。

六.参考链接

1. https://www.cnblogs.com/hengzhou/p/9896535.html