我认为创建了一个包含 N+1 个项目的新 ImmutableList。因此它的复杂度应该是 O(N)。
问问题
972 次
1 回答
6
此处解释了 ImmutableList 具有 O(log n) 复杂性的原因：
为什么在可变类型为 O(1) 的情况下，不可变类型更容易出现 O(log n) 时间？这是允许跨集合实例共享的内部数据结构的结果。例如，可变 HashSet 分配一个数组，并将该数组中的元素存储在由其哈希码确定的索引处。这提供了 O(1) 的查找和存储时间。如果 ImmutableHashSet 使用这种相同类型的数据存储，那么每个突变都需要重新分配和复制整个数组以更改一个条目，随着集合变得越来越大，这将迅速降低性能和 GC 压力。相反，这些不可变的集合使用 不可变的平衡二叉树来存储它们的数据，允许在集合的变异实例之间进行非常有效的数据共享。然而，结果是，每次查找或更改都需要一个树遍历，它（在最坏的情况下）具有 O(log n) 的算法复杂度。
ImmutableArray的MSDN 文档提供了一些见解，并显示了 ImmutableArray 和 ImmutableList 之间的复杂性差异：
于 2016-05-18T15:47:45.713 回答