.NET集合类的渐近复杂性

Question

是否存在有关的.NET集合类的方法渐近复杂性(大O,其余)的任何资源(Dictionary<K,V>,List<T>等...)？

我知道C5库的文档包含了一些关于它的信息(示例),但我也对标准.NET集合感兴趣...(而且PowerCollections的信息也很好).

Answer 1

MSDN列出这些:

• Dictionary<,>
• List<>
• SortedList<,>(编辑:错误链接;这是通用版本)
• SortedDictionary<,>

等.例如:

SortedList(TKey,TValue)泛型类是具有O(log n)检索的二叉搜索树,其中n是字典中元素的数量.在这里,它类似于SortedDictionary(TKey,TValue)泛型类.这两个类具有相似的对象模型,并且都具有O(log n)检索.两个类别的不同之处在于内存使用和插入和移除速度:

SortedList(TKey,TValue)比SortedDictionary(TKey,TValue)使用更少的内存.

SortedDictionary(TKey,TValue)对未排序数据(O(log n))的排序和删除操作更快,而对于SortedList(TKey,TValue)则为O(n).

如果列表是从排序数据中一次性填充的,则SortedList(TKey,TValue)比SortedDictionary(TKey,TValue)快.

Answer 2

这个页面总结了使用Java的各种集合类型的一些时间复杂性,尽管它们对于.NET应该完全相同.

我从该页面获取了表格,并为.NET框架更改/扩展了它们.另请参阅SortedDictionary和SortedList的MSDN页面,其中详细说明了各种操作所需的时间复杂性.

搜索

Type of Search/Collection Types           Complexity  Comments
Linear search Array/ArrayList/LinkedList  O(N)        Unsorted data.
Binary search sorted Array/ArrayList/     O(log N)    Requires sorted data.
Search Hashtable/Dictionary<T>            O(1)        Uses hash function.
Binary search SortedDictionary/SortedKey  O(log N)    Sorting is automated.

检索和插入

Operation         Array/ArrayList  LinkedList  SortedDictionary  SortedList
Access back       O(1)             O(1)        O(log N)          O(log N)
Access front      O(1)             O(1)        N.A.              N.A.
Access middle     O(1)             O(N)        N.A.              N.A.
Insert at back    O(1)             O(1)        O(log N)          O(N)
Insert at front   O(N)             O(1)        N.A.              N.A.
Insert in middle  O(N)             O(1)        N.A.              N.A.

删除应该与关联集合的插入具有相同的复杂性.

SortedList具有一些值得注意的插入和检索特性.

插入(添加方法):

此方法是未排序数据的O(n)操作,其中n为Count.如果在列表末尾添加新元素,则为O(log n)操作.如果插入导致调整大小,则操作为O(n).

检索(项目属性):

检索此属性的值是O(log n)操作,其中n是Count.如果该键已经在SortedList <(Of <(TKey,TValue>)>)中,则设置该属性是O(log n)操作.如果密钥不在列表中,则设置属性是对未排序数据的O(n)操作,如果在列表末尾添加新元素,则设置O(log n).如果插入导致调整大小,则操作为O(n).

注意,这ArrayList相当于List<T>所有操作的复杂性.