是否有任何关于 .NET 集合类方法的渐近复杂性(big-O 和其他)的资源(Dictionary<K,V>
, List<T>
ETC...)?
我知道 C5 库的文档包含一些有关它的信息(example),但我也对标准 .NET 集合感兴趣...(PowerCollections 的信息也很好)。
MSDN 列出了这些:
- Dictionary<,>
- List<>
-
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)比
排序字典(TKey,TValue)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)