c# - 为什么 ImmutableList 的 add 方法复杂度为 O(logN)？

Question

我认为创建了一个包含 N+1 项的新 ImmutableList。因此它的复杂度应该是O(N)。

Answer 1

ImmutableList复杂度为O(log n)的原因详解here :

Why are the immutable types more prone to O(log n) time where mutable types are O(1)? It’s a consequence of the internal data structures that allow sharing across instances of the collections. For instance a mutable HashSet allocates a single array, and stores elements in that array at the index determined by their hash code. This providers O(1) lookup and storage times. If an ImmutableHashSet used this same kind of data storage, then every mutation would require reallocating and copying the entire array just to change one entry, which would quickly tank performance and GC pressure as the collections grew large. Instead, these immutable collections use immutable balanced binary trees to store their data, allowing very efficient data sharing across mutated instances of the collections. As a result however, every lookup or change requires a tree traversal that has (at worst) an algorithmic complexity of O(log n).

MSDN documentation for ImmutableArray提供了一些见解并显示了 ImmutableArray 和 ImmutableList 之间的复杂性差异: