34

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

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

4

6 回答 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) 快。

于 2009-05-12T09:34:00.170 回答
32

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

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

搜索

搜索类型/集合类型 复杂性 注释
线性搜索 Array/ArrayList/LinkedList O(N) 未排序的数据。
Binary search sorted Array/ArrayList/ O(log N) 需要已排序的数据。
Search Hashtable/Dictionary<T> O(1) 使用散列函数。
二进制搜索 SortedDictionary/SortedKey O(log N) 排序是自动的。

检索和插入

操作 Array/ArrayList LinkedList SortedDictionary SortedList
返回 O(1) O(1) O(log N) O(log N)
访问前 O(1) O(1) NANA
访问中间 O(1) O(N) NANA
在后面插入 O(1) O(1) O(log N) O(N)
在前面插入 O(N) O(1) NANA
插入中间 O(N) O(1) NANA

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

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>

于 2009-05-12T09:38:48.870 回答
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)；至于它实际上是什么......好吧，我的头很痛，无法找到:)

于 2011-06-15T12:45:35.683 回答
2

本页简要介绍了大多数 .NET 集合的一些主要优点和缺点：

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

收藏 订购 连续存储 直接访问 查找效率 操纵效率 笔记
字典 无序 是的 通过密钥 键：O(1) O(1) 最适合高性能查找。
排序字典 已排序 不 通过密钥 键：O(log n) O(log n) 字典速度和排序的妥协，使用二叉搜索树。
排序列表 已排序 是的 通过密钥 键：O(log n) 上） 与 SortedDictionary 非常相似，除了树是在数组中实现的，因此对预加载数据的查找速度更快，但加载速度较慢。
列表 用户可以精确控制元素排序 是的 通过索引 索引：O(1)
值：O(n)		 上） 最适合需要直接访问且无需排序的较小列表。
链表 用户可以精确控制元素排序 不 不 值：O(n) O(1) 最适合在中间插入/删除很常见且不需要直接访问的列表。
哈希集 无序 是的 通过密钥 键：O(1) O(1) 唯一的无序集合，就像字典一样，除了键和值是同一个对象。
排序集 已排序 不 通过密钥 键：O(log n) O(log n) 唯一的排序集合，就像 SortedDictionary 一样，除了键和值是同一个对象。
堆 后进先出 是的 只有顶部 顶部：O(1) O(1)* 与 List 基本相同，只是仅作为 LIFO 处理
队列 先进先出 是的 只有前面 前：O(1) O(1) 与 List 基本相同，只是仅作为 FIFO 处理
于 2015-08-18T07:58:34.597 回答
0

没有“集合类的复杂性”之类的东西。相反，对这些集合的不同操作具有不同的复杂性。例如，将元素添加到Dictionary<K, V>...

...接近O(1)操作。如果必须增加容量以容纳新元素，则此方法变为O(n)操作，其中nis Count。

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

...接近 O(1) 操作。

于 2009-05-12T09:35:58.593 回答
0

文档说它是建立在二叉树上的，并且没有提到跟踪最大元素。如果文档是正确的，这意味着它应该是 O(log n)。集合文档中曾经至少存在一个错误（将数组支持的数据结构称为二叉搜索树），但已更正。

于 2011-06-29T13:56:21.767 回答