什么是字典的时空复杂度

添加新

条目的时间复杂度记录在 Dictionary<T>.Add() 下：

如果 Count 小于容量，则此方法接近 O（1） 操作。如果必须增加容量以容纳新元素，则此方法将成为 O（n） 操作，其中 n 是 Count。

空间的复杂性是什么——整个字典

字典使用具有 O（N） 空间复杂度的关联数组数据结构。

Msdn 说："字典类是作为哈希表实现的"。哈希表依次使用关联数组。

时间的复杂性是什么——在字典中添加条目

单次添加需要摊销 O（1） 时间。在大多数情况下，它是 O（1），当底层数据结构需要增长或收缩时，它会更改为 O（N）。由于后者很少发生，人们使用"摊销"一词。

它没有正式的文档，但广泛声明（并通过反汇编可见）底层存储是名称-值对的数组。因此空间复杂度为 O（n）。

由于它不是规范的一部分，这在理论上可以改变;但在实践中不太可能改变，因为它会改变可能可见的各种操作（例如枚举）的性能。