基本Java容器上的CRUD操作的渐进复杂性是什么 [英] What is asymptotic complexity for CRUD operations on basic Java containers

问题描述

我试图弄清楚Java基本集合上操作的复杂性(使用big-o表示法).与此C ++语言问题中的操作类似.

I am trying to figure out what are the complexities (using the big-o notation) of operations on Java basic collections. Similarly as in this question for C++ language.

使用常识，这就是我所拥有的:

Here is what I have, using the common sense:

• add(E e) O(1)
• add(int index，E e) O(n)
• set(int索引，E元素 O(1)
• get(int索引) O(1)
• 删除(E e)删除(int索引) O(n)
• 包含(E e) O(n)
• 列表串联(addAll) O(n)

• add(E e) O(1)
• add(int index, E e) O(n)
• set(int index, E element O(1)
• get(int index) O(1)
• remove(E e) remove(int index) O(n)
• contains(E e) O(n)
• list concatenation (addAll) O(n)

• add(E e) O(1)
• add(int index，E e) O(n)
• set(int索引，E元素 O(n)
• get(int索引) O(n)
• 删除(E e)删除(int索引) O(n)
• 包含(E e) O(n)
• 列表串联(addAll) O(1)

• add(E e) O(1)
• add(int index, E e) O(n)
• set(int index, E element O(n)
• get(int index) O(n)
• remove(E e) remove(int index) O(n)
• contains(E e) O(n)
• list concatenation (addAll) O(1)

• add(E e) O(1)
• 删除(E e) O(1)
• 包含(E e) O(1)
• 使用迭代器 O(n)
查找/获取元素

• add(E e) O(1)
• remove(E e) O(1)
• contains(E e) O(1)
• find/get an element using iterator O(n)

• add(E e) O(log n)
• 删除(E e) O(log n)
• 包含(E e) O(log n)
• addAll O(n log n)
• 在执行二进制搜索时，使用迭代器 O(n)或 O(log n)查找元素

• add(E e) O(log n)
• remove(E e) O(log n)
• contains(E e) O(log n)
• addAll O(n log n)
• find an element using iterator O(n) or perhaps O(log n) when implementing the binary search

• 放置(K键，V值) O(1)
• 获取(K键) O(1)
• 删除(E e) O(1)
• containsKey(对象密钥) O(1)
• 包含值(对象值) O(n)
• putAll O(n)
• 使用迭代器 O(n)或也许 O(log n)查找/获取元素，与TreeSet
中的相同

• put(K key, V value) O(1)
• get(K key) O(1)
• remove(E e) O(1)
• containsKey(Object key) O(1)
• containsValue(Object value) O(n)
• putAll O(n)
• find/get an element using iterator O(n) or perhaps O(log n) same as in TreeSet

• 放置(K键，V值) O(log n)
• 获取(K键) O(登录n)
• 删除(E e) O(log n)
• containsKey(对象密钥) O(log n)
• 包含值(对象值) O(n)
• putAll O(n log n)
• 使用迭代器 O(n)
查找/获取元素

• put(K key, V value) O(log n)
• get(K key) O(log n)
• remove(E e) O(log n)
• containsKey(Object key) O(log n)
• containsValue(Object value) O(n)
• putAll O(n log n)
• find/get an element using iterator O(n)

注意:基于哈希的集合假定设计良好的哈希函数位于 O(1)中，否则位于 O(n) 中

NOTE: Collections based on hashing assume well designed hash function to be in O(1) otherwise it is in O(n)

问题: 这是正确的吗?

推荐答案

关于此方面的最佳知识就是文档.这是我可以通过一两个快速搜索找到的内容.

Your best source of knowledge about this would be the documentation. Here is what I could find with a quick search or two.

size，isEmpty，get，set，iterator和listIterator操作在恒定时间内运行. add操作以摊销的恒定时间运行，也就是说，添加n个元素需要O(n)时间.所有其他操作都是线性运行的(大致而言).

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

LinkedList

所有操作均按双向链接列表的预期执行.索引到列表中的操作将从列表的开头或结尾开始遍历列表，以更接近指定索引的位置为准.

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

根据我记得的有关双链表的信息，我会说您的常识​​假设"是正确的.

From what I remember about doubly-linked lists, I would say your "common sense assumption" is correct.

该类为基本操作(添加，删除，包含和大小)提供恒定的时间性能，假设哈希函数将元素正确分散在存储桶中.对该集合进行迭代需要的时间与HashSet实例的大小(元素数)之和再加上HashSet实例的容量"之和成正比.支持的HashMap实例的数量(存储桶数).

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets).

LinkedHashSet

像HashSet一样，它为基本操作(添加，包含和删除)提供恒定时间的性能，假设哈希函数将元素正确地分散在存储桶中.由于维护链接列表会增加开销，因此性能可能会略低于HashSet，但有一个例外:在LinkedHashSet上进行迭代需要的时间与集合的大小成正比，而无论其容量如何.在HashSet上进行迭代可能会更昂贵，需要的时间与其容量成正比.

Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

TreeSet

此实现为基本操作(添加，删除和包含)提供了保证的log(n)时间成本.

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

地图

HashMap

该实现为基本操作(获取和放置)提供恒定时间的性能，假设哈希函数将元素正确分散在存储桶中.集合视图上的迭代需要与容量"成正比的时间. HashMap实例的数量(存储桶的数量)加上其大小(键-值映射的数量).

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

LinkedHashMap

像HashMap一样，它为基本操作(添加，包含和删除)提供恒定时间的性能，假设哈希函数将元素正确地分散在存储桶中.性能可能会略低于HashMap，...

Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap,...

TreeMap

此实现为containsKey，get，put和remove操作提供了保证的log(n)时间成本.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

如果未提及某些方法，请尝试查找该特定方法.如果文档中未提及运行时间，则可能与实现有关.

If some of the methods are not mentioned, try to look up that specific method. If the running time is not mentioned anywhere in the documentation, it might be implementation dependent.

这篇关于基本Java容器上的CRUD操作的渐进复杂性是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！