.NET 集合类的渐近复杂度

Question

是否有关于 .NET 集合类（Dictionary、List 等方法的渐近复杂性（big-O 和其他）的资源...）？

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

Answer 1

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

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

---

搜索

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 是计数。 这是
一个 O(log n) 操作，如果新的
元素被添加到末尾
列表。 如果插入导致调整大小，
该操作是 O(n)。

检索（项目属性）：

检索该属性的值
是一个 O(log n) 运算，其中 n 是
数数。 设置属性是
O(log n) 操作，如果密钥是
已经在 SortedList<(Of <(TKey,
T值>)>)。 如果密钥不在
列表，设置属性是 O(n)
对未排序数据的操作，或 O(log
n) 如果新元素添加到
列表末尾。 如果插入导致
调整大小，操作是O(n)。

请注意，就所有操作的复杂性而言，ArrayList 与 List 等效。

---

Answer 2

MSDN 列出了这些：

• 字典<,>
• 列表
• SortedList<,>（编辑：错误的链接；这是通用版本）
• SortedDictionary<,>

等。例如：

SortedList(TKey, TValue) 泛型
class 是一个二叉搜索树
O(log n) 检索，其中 n 是
字典中的元素数量。
在这一点上，它类似于
SortedDictionary(TKey, TValue) 泛型
班级。 两个类有相似之处
对象模型，并且都有 O(log n)
恢复。 两个班级在哪里
不同之处在于内存使用和速度
插入和删除：

SortedList(TKey, TValue) 使用较少
内存比 SortedDictionary(TKey,
T值）。

SortedDictionary(TKey, TValue) 有
更快的插入和移除
对未排序数据的操作，O(log n)
与 O(n) 相反
排序列表（TKey，TValue）。

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

Answer 3

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

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

<表类=“s-表”>
<标题>

集合
排序
连续存储
直接访问
查找效率
操纵效率
注释

<正文>

字典
无序
是
通过按键
密钥：O(1)
O(1)
最适合高性能查找。

排序字典
已排序
否
通过按键
键：O(log n)
O(log n)
妥协字典速度和排序，使用二叉搜索树。

排序列表
已排序
是
通过按键
键：O(log n)
O(n)
与 SortedDictionary 非常相似，不同之处在于树是在数组中实现的，因此对预加载数据的查找速度更快，但加载速度较慢。

列表
用户可以精确控制元素排序
是
通过索引
索引：O(1)
值：O(n)
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 进行处理

Answer 4

我一般不知道（刚刚发布的另一个答案可能准确地给出了您所追求的内容） - 但您当然可以使用 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)； 至于它到底是什么......好吧，我的头太痛了，无法找出答案:)

Answer 5

不存在“集合类的复杂性”这样的事情。 相反，对这些集合的不同操作具有不同的复杂性。 例如，将元素添加到 Dictionary...

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

而从 Dictionary 检索元素...

...接近 O(1) 运算。

Answer 6

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