c# - Dictionary 的时间和空间复杂度是多少？

Question

假设我有大小为 N 的数据(即 N 个元素)，并且字典是用容量 N 创建的。 的复杂性是什么:

空间--整个字典

时间 -- 添加词条到字典

MS 仅显示条目检索接近 O(1)。但是剩下的呢？

Answer 1

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

If Count is less than the capacity, this method approaches an O(1) operation. If the capacity must be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.