.NET集合类的渐近复杂性 [英] Asymptotic complexity of .NET collection classes

问题描述

有关于.NET集合类的渐近复杂性（big-O和其他方法）的任何资源（ Dictionary< K，V> ， List< T> 等...）？

Are there any resources about the asymptotic complexity (big-O and the rest) of methods of .NET collection classes (Dictionary<K,V>, List<T> etc...)?

我知道C5库的文档包括一些信息href =http://www.itu.dk/research/c5/Release1.1/c5doc/types/C5.LinkedList_1.htm =nofollow noreferrer> example ），但我很感兴趣在标准的.NET集合太...（和PowerCollections的信息也会很好）。

I know that the C5 library's documentation includes some information about it (example), but I'm interested in standard .NET collections too... (and PowerCollections' information would also be nice).

推荐答案

MSDN列出以下内容：

MSDN Lists these:

• 字典<，>


• 列表<>


• SortedList<，> （编辑：错误链接;这里是通用版本）


• SortedDictionary<，>

• Dictionary<,>
• List<>
• SortedList<,> (edit: wrong link; here's the generic version)
• SortedDictionary<,>

等。例如：

SortedList（TKey，TValue）generic
类是一个二叉搜索树，其中包含
O log n）检索，其中n是字典中元素的
数。
在这里，它类似于
SortedDictionary（TKey，TValue）generic
类。这两个类有类似的
对象模型，并且都有O（log n）
检索。其中两个类
不同是在
的内存使用和速度插入和删除：

The SortedList(TKey, TValue) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary(TKey, TValue) generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

SortedList（TKey，TValue）使用较少
记忆比SortedDictionary（TKey，
TValue）。

SortedList(TKey, TValue) uses less memory than SortedDictionary(TKey, TValue).

SortedDictionary（TKey，TValue）有
更快的插入和删除
操作未分类数据，O（log n）
，而不是
SortedList（TKey，TValue）的O（n）。

SortedDictionary(TKey, TValue) has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList(TKey, TValue).

从排序数据一次填充所有的
，SortedList（TKey，
TValue）比
更快SortedDictionary（TKey，TValue）。

If the list is populated all at once from sorted data, SortedList(TKey, TValue) is faster than SortedDictionary(TKey, TValue).

这篇关于.NET集合类的渐近复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！