.NET 集合類的漸近複雜度

是否有關於 .NET 集合類（等）的方法的漸近複雜性（big-O 和其他）的任何Dictionary<K,V>資源List<T>？

我知道 C5 庫的文件包含一些有關它的資訊（範例），但我也對標準 .NET 集合感興趣……（並且 PowerCollections 的資訊也很好）。

MSDN 列出了這些：

• Dictionary<,>
• List<>
• SortedList<,>（編輯：錯誤的連結；這是通用版本）
• SortedDictionary<,>

等等例如：

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) 快。

引用自：https://stackoverflow.com/questions/851949