logo标签列表

.NET集合类的渐近复杂度

.netcollectionsbig-oasymptotic-complexity
34

有没有关于.NET集合类(Dictionary<K,V>, List<T> 等等) 方法渐近复杂度 (大O表示法等) 的相关资源?

我知道C5库的文档包括一些相关信息(例子)，但我也对标准.NET集合类感兴趣...(还有 PowerCollections 的信息也不错)。

在考虑一个类的复杂度时，我会考虑圈复杂度而不是渐进时间/空间复杂度。我会将后者归因于类内部的操作。 - pugmarx
您可以编写一个程序来测量您感兴趣的特定函数，将结果针对不同的输入模式绘制成N。我认为时间复杂度没有被记录下来的主要原因是这是一个实现细节，因此.NET团队保留在将来更改实现特定内容的权利。因此，这些类的规范基于它们的功能而不是性能。如果某个具体的性能特征对您的要求非常重要，则最好自己实现算法。 - Dan Bryant
6个回答
33

MSDN列出了以下内容：

等等。例如：

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)更快。

1
在这个（旧的，已删除的）引用中，二叉搜索树被与基于排序数组的集合混淆了。http://en.wikipedia.org/wiki/Binary_search_tree - Stephan Eggermont
“Dictionary<TKey, TValue>”泛型类提供了从一组键到一组值的映射。每次向字典中添加元素时，都需要提供一个值和其关联的键。通过使用键检索值非常快，接近于O(1)，因为“Dictionary<TKey, TValue>”类是作为哈希表实现的。请注意它们列出的O符号。” - Chris Lucian
33

本页面总结了Java中各种集合类型的一些时间复杂度，尽管它们对于.NET应该完全相同。

我从那个页面上获取了表格，并为.NET框架进行了修改/扩展。 另请参阅MSDN页面SortedDictionary和SortedList，其中详细说明了各种操作所需的时间复杂度。

查找

搜索类型/集合类型           复杂度  说明
线性搜索 数组/ArrayList/LinkedList   O(N)        未排序的数据。
二分搜索 已排序的数组/ArrayList/     O(log N)    需要排序的数据。
搜索 Hashtable/Dictionary<T>            O(1)        使用哈希函数。
二分搜索 SortedDictionary/SortedKey  O(log N)    自动排序。

检索和插入

操作         数组/ArrayList  LinkedList  SortedDictionary  SortedList
访问末尾       O(1)             O(1)        O(log N)          O(log N)
访问开头       O(1)             O(1)        N.A.              N.A.
访问中间       O(1)             O(N)        N.A.              N.A.
在末尾插入     O(1)             O(1)        O(log N)          O(N)
在开头插入     O(N)             O(1)        N.A.              N.A.
在中间插入     O(N)             O(1)        N.A.              N.A.

删除应与相应集合的插入具有相同的复杂度。

SortedList在插入和检索方面有一些值得注意的特殊情况。

插入（Add方法）：

对于未排序的数据，此方法是一个O(n)操作，其中n是Count。如果新元素添加到列表末尾，则它是一个O(log n)操作。如果插入导致调整大小，则操作为O(n)。

检索（Item属性）：

检索该属性的值是 O(log n) 操作，其中 n 是 Count。如果键已经在 SortedList<(Of <(TKey, TValue)>)> 中，设置属性是 O(log n) 操作。如果键不在列表中，则对于未排序的数据，设置该属性是 O(n) 操作，或者如果新元素添加到列表末尾，则是 O(log n) 操作。如果插入导致调整大小，则操作为 O(n)。请注意，所有操作的复杂度方面，ArrayList 等效于 List。
5
你确定.NET中的复杂性应该是相同的吗？我认为情况比这更微妙——例如，在.NET中，SortedDictionary、SortedList和Hashtable之间存在差异。 - Igor Brejc
是的，基本算法和数据结构几乎完全相同，没有根本区别。我还没有详细介绍SortedDictionary/SortedList，但我现在会加上它们。我相信Hashtable应该与Dictionary具有相同的复杂度（它几乎是其非泛型版本）。 - Noldorin
绝对不能保证底层实现是可比较的。 - Tanveer Badar
1
不是，但这确实是官方的.NET实现情况。 - Noldorin
4
这个页面介绍了大多数.NET集合的一些关键优缺点的简短注释：

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx


收集，排序，连续存储，直接访问，查找效率和操作效率的比较表： | 收集 | 排序 | 连续存储 | 直接访问 | 查找效率 | 操作效率 | 注释 | | ---------- | ------ | -------- | -------- | ---------- | -------- | ------------------------------------------------------------ | | Dictionary | 无序 | 是 | 通过键值 | 键: O(1) | O(1) | 最适合高性能查找。 | | SortedDictionary | 排序 | 否 | 通过键值 | 键: O(log n) | O(log n) | 查找速度和排序之间的折衷，使用二叉搜索树。 | | SortedList | 排序 | 是 | 通过键值 | 键: O(log n) | O(n) | 与SortedDictionary非常相似，但树是在数组中实现的，因此在预加载数据上具有更快的查询速度，但加载较慢。 | | List | 用户有精确控制流元素排序 | 是 | 通过索引 | 索引：O(1)
值：O(n) | O(n) | 最适合需要直接访问且不需要排序的较小列表。 | | LinkedList | 用户有精确控制流元素排序 | 否 | 否 | 值：O(n) | O(1) | 最适合需要经常在中间插入/删除且不需要直接访问的列表。 | | HashSet | 无序 | 是 | 通过键值 | 键: O(1) | O(1) | 唯一无序集合，类似于Dictionary，但键和值是相同的对象。 | | SortedSet | 排序 | 否 | 通过键值 | 键: O(log n) | O(log n) | 唯一排序集合，类似于SortedDictionary，但键和值是相同的对象。 | | Stack | LIFO | 是 | 仅顶部 | 顶部: O(1) | O(1)* | 与List基本相同，只处理LIFO。 | | Queue | FIFO | 是 | 仅前面 | 前: O(1) | O(1) | 与List基本相同，只处理FIFO。 |
1
链接已经失效，因此最好引用相关内容，因为现在人们无法参考这些可能有用的信息。 - Larry Smith
1
幸运的是，互联网档案馆在这里备份了：https://web.archive.org/web/20121022141414/http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx - KMR
2

我不确定一般情况下是怎样的（也许其他答案已经给出了你需要的答案）- 但是你当然可以使用ILSpy反映这个和其他方法（对于FSharp代码有点棘手，确实），最终将其转换为C#函数：

internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
  while (true)
  {
    SetTree<a> setTree = s;
    if (setTree is SetTree<a>.SetOne)
    {
      break;
    }
    if (setTree == null)
    {
      return n;
    }
    SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
    SetTree<a> arg_23_0 = setNode.item3;
    n = setNode.item1;
    s = arg_23_0;
  }
  return ((SetTree<a>.SetOne)s).item;
  return n;
}

好的，所以从C#角度来说这并不是"合适"的代码 - 但是存在while(true)循环表明它至少不可能是O(1); 至于它到底是什么... 好吧，我的头疼得太厉害了，无法找出答案 :)

FYI: 合并自http://stackoverflow.com/questions/6313896/net-framework-time-complexity-in-the-documentation - Shog9
0
文档显示它是建立在二叉树上的，没有提到跟踪最大元素。如果文档是正确的，那么它应该是O(log n)的。集合文档曾经至少有一个错误（将支持数组的数据结构称为二叉搜索树），但已经被纠正了。
1
公平地说，数组是一个完全合理的存储二叉树的方式。详情请见：http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html - Mike Caron
是的和不是的。是的，因为它当然都映射到主内存中，提供了类似于数组的接口（但非常偏向于优先访问同一缓存行中的数据）。但对于除最小（且平衡）的树之外，这并不提供合理的实现。多路树更适合当前的处理器设计。 - Stephan Eggermont
FYI：合并自http://stackoverflow.com/questions/6313896/net-framework-time-complexity-in-the-documentation - Shog9
0

“集合类的复杂性”并不存在。相反，对这些集合的不同操作具有不同的复杂度。例如，向 Dictionary<K, V>... 添加一个元素...

…是一个 O(1) 操作。如果必须增加容量以容纳新元素，则此方法变为一个 O(n) 操作，其中 n 是 Count。

而从 Dictionary<K, V>... 中检索元素...

…是一个 O(1) 操作。

1
我的意思是他们的操作，我已经编辑了问题以使其更清晰。 - Igor Brejc
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接