添加到集合O(n)？

Question

由于集合只能具有唯一值,这是否意味着每次向元素添加元素时都必须检查它是否等于那里的每个元素,因此是O(n)？

因为如果是这种情况,这会使它们比arrayLists慢很多,那么你应该真正使用它们的唯一时间是确保你的元素都是唯一的还是它们还有其它优点？

Answer 1

这取决于a的实现set.

C++

一个std::set在C++中通常被实现为一个红黑树,保证的O插入的复杂性(的log(n))(源).

std :: set是一个关联容器,包含一组有序的Key类型的唯一对象.使用密钥比较功能比较进行排序.搜索,删除和插入操作具有对数复杂性.

C++ 11的std::unordered_set插入复杂度为O(1)(源).

无序集是一个关联容器,包含一组Key类型的唯一对象.搜索,插入和删除具有平均的恒定时间复杂度.

JAVA

在Java中,向a添加元素HashSet是O(1).从文档:

该类为基本操作(添加,删除,包含和大小)提供恒定的时间性能,假设散列函数在桶中正确地分散元素

将元素插入a TreeSet是O(log(n)).

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

所有实现的类Set都可以在文档中找到.

结论

set在大多数情况下,添加到a 并不比添加到ArrayList或更慢std::vector.但是,a set不一定按照插入顺序保留项目.此外,访问集合中的某些第N个元素的复杂性比对ArrayListor 的相同操作更复杂std::vector.每种都有其优点和缺点,应相应使用.