目录
  1. 引言
  2. 1、 List
    1. 1.1、ArrayList
    2. 1.2、LinkedList
  3. 2、Set
    1. 2.1、HashSet
    2. 2.2、TreeSet
    3. 2.3、LinkedHashSet
  4. 3、Map
  5. 参考
Java集合类时间复杂度分析

引言

渐进时间复杂度的概念:
若存在函数 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

文章作者: ClawHub
文章链接: https://www.clawhub.club/posts/2019/12/25/JAVA%E5%9F%BA%E7%A1%80%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6/Java%E9%9B%86%E5%90%88%E7%B1%BB%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ClawHub的博客
打赏
  • 微信
  • 支付宝
扫一扫关注ClawHub公众号,专注Java、技术分享、面试资源。