引言

渐进时间复杂度的概念：
若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

时间复杂度推导原则：

  • 如果运行时间是常数量级，用常数1表示。
  • 只保留时间函数中的最高阶项。
  • 如果最高阶项存在，则省去最高阶项前面的系数。

1、 List

1.1、ArrayList

  • add(E e)方法直接在数组尾部插入，时间复杂度为O(1)
  • add(int index, E element)方法指定索引插入，会有数据的移动，时间复杂度为O(n)
  • get(int index)根据数组下标获取，时间复杂度O(1)
  • remove(int index)删除后，数据会存在移动，时间复杂度O(n)

1.2、LinkedList

  • add(E e) 尾插法，时间复杂度为O(1)
  • add(int index, E element)在指定位置插入，需要循环获取插入位置，时间复杂度O(n)
  • get(int index)获取指定位置节点，序遍历链表，时间复杂度为O(n)
  • remove() 删除头节点，时间复杂度O(1)

2、Set

2.1、HashSet

  • add(E e)底层就是HashMap的 put(K key, V value)方法，JDK1.8引入了红黑树，当hash表中的节点链表长度达到树化阈值8时，会转化为红黑树，插入时间复杂度为O(logn)。

只要引入了红黑树，插入、删除、查找时，时间复杂度都会变为O(logn)。

2.2、TreeSet

底层为TreeMap，使用红黑树实现，插入删除查找时间复杂度为O(logn)。

2.3、LinkedHashSet

LinkedHashSet继承自LinkedHashSet，最底层为LinkedHashMap，而LinkedHashMap继承自HashMap，所以时间复杂度分析与HashMap相同。

3、Map

常见的三个实现类HashMap，TreeMap，LinkedHashMap，底层都引入了红黑树，时间复杂度相应的也随着红黑树，插入、删除、查找都为O(logn)。

参考

一套图 搞懂“时间复杂度”
JAVA集合时间复杂度
红黑树(一)之 原理和算法详细介绍

tencent.jpg