C#常用集合类的实现以及基本操作复杂度

List 集合类是顺序线性表,Add操作是O(1)或是O(n)的,由于List的容量是动态扩容的,在未扩容之前,其Add操作是O(1),而在需要扩容的时候,会拷贝已存在的那些元素同时添加新的元素,此时的Add操作是O(n)的。而对于Contains方法,其是按照线性检索的,其复杂度是O(n)。而BinarySearch方法,其是按二分查找的,其复杂度是O(lg n)。

SortedList集合类是有序线性表,Add操作是O(n), 其Contains方法是通过二分查找检索元素的,因此复杂度是O(lg n),其Containskey方法也是通过二分查找检索元素,复杂度也是O(lg n),ContainsValue方法是使用线性查找元素,复杂度是O(n)。

Dictionary集合类是hash表,Add操作是O(1)或是O(n)的,原因同上。其Containskey方法是O(1),原因是通过hash来查找元素而不是遍历元素。ContainsValue方法的时间复杂度是O(n),原因是内部通过遍历key来查找value,而不是通过hash来查找。Item[Key]属性根据key来检索value,其时间复杂度也是O(1)。

SortedDictionary集合类是基于平衡二叉树实现的,其Add方法是O(lg n),ContainsKey方法也是O(lg n),而ContainsValue方法则是O(n)。

HashSet集合类是包含不重复项的无序hash表(非线性表)。Add操作是O(1)或是O(n)的,原因同List集合类。Contains方法是O(1)。HashSet是Set集合,它只实现了ICollection接口,在单独元素访问上,有很大的限制:   

    1、跟List相比,不能使用下标来访问元素,如:list[1] 。       

    2、跟Dictionary相比,不能通过键值来访问元素,例如:dic[key],因为HashSet每条数据只保存一项,并不采用Key-Value的方式,换句话说,HashSet中的Key就是Value,假如已经知道了Key,也没必要再查询去获取Value,需要做的只是检查值是否已存在。

SortedSet集合类是基于红黑树实现的,其Add方法是O(lg n),Contains方法也是O(lg n)

 目前只涉及到Add以及Contains等检索方法,后续可能会补充上删除等操作的复杂度。

参考:

真是O(1)吗?想清楚了没?

C# SortedDictionary以及SortedList的浅谈

你真的了解字典(Dictionary)吗?

C#常用集合类的实现以及基本操作复杂度

上一篇:使用yaml+groovy实现Java代码可配置化


下一篇:C# 保存文件