.NET 集合类的渐近复杂度

StackOverflow https://stackoverflow.com/questions/851949

题

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

我知道 C5 库的文档包含一些有关它的信息（例子），但我也对标准 .NET 集合感兴趣......（PowerCollections 的信息也很好）。

有帮助吗？

解决方案

MSDN 列出了这些：

ETC。例如：

SortedList（TKey， TValue） 泛型 class 是一个二叉搜索树，具有 O（log n） 检索，其中 n 是 字典中的元素数。在这一点上，它类似于 SortedDictionary（TKey， TValue） 泛型 类。这两个类具有相似的 对象模型，并且两者都具有 O（log n） 检索。其中两个类 不同之处在于内存使用和速度 插入和移除：

SortedList（TKey， TValue） 使用较少 内存比 SortedDictionary（TKey， TValue）。

SortedDictionary（TKey， TValue） 有 更快的插入和拔出 未排序数据的操作，O（log n） 与 O（n） 相反 SortedList（TKey， TValue）。

如果一次填充所有列表 从排序数据中，SortedList（TKey， TValue）比 SortedDictionary（TKey， TValue）。

其他提示

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

我从该页面获取了表格，并针对 .NET 框架更改/扩展了它们。另请参阅 MSDN 页面 排序字典 和 排序列表, ，其中详细说明了各种操作所需的时间复杂度。

搜寻中

搜索/集合类型 复杂性 注释
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.

检索和插入

操作 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是计数的。如果在列表的末尾添加了新元素，则是O（log n）操作。如果插入导致调整大小，则操作为O（n）。

检索（项目属性）：

检索此属性的值是O（log n）操作，其中n为计数。设置属性是O（log n）操作，如果键已经在sortedlist <（of <（tkey，teke，tvalue>）>）中。如果密钥不在列表中，则设置属性是未分类数据的O（n）操作，或者如果在列表末尾添加了新元素，则将o（log n）设置为O（log N）。如果插入导致调整大小，则操作为O（n）。

注意 ArrayList 相当于 List<T> 就所有操作的复杂性而言。

我不知道在一般的（对方的回答只是贴或许给你你到底是什么后） - 但可以反映出这一点，并使用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）至少;至于它实际上是什么......嗯，我的头伤得太深，找出：）

有是为“集合类的复杂性”没有这样的事。相反，在这些集合不同的业务有不同的复杂性。例如，将一个元素增加到一个Dictionary<K, V> ...

  

...接近的 O（1）操作。如果容量必须增加，以适应新的元件，该方法成为一种 O（n）的操作，其中n是Count。

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

  

...接近的O（1）的操作。

文档说，这是建立在一个二叉树，并没有提到跟踪最大元素。如果文件是正确的，这意味着它应该是O（log n）的。曾经有集合文档（指阵列支持的数据结构的二进制搜索树）中的至少一个错误，但已被纠正。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top