如果我不指定容量，将 N 个元素插入到 List<T> 中的复杂度顺序是什么？

Question

假设我有类似

的东西

List<int>() numbers = new List<int>();
int num;
while(int.TryParse(Console.ReadLine(), out num))
{
    numbers.Add(num);
}

假设添加的元素数量为 N。我想知道在考虑到插入是 "usually" O(1) 但将是 O(n) "once in a while" 当内部需要将列表复制到更大的数组时。

Answer 1

这完全取决于此框架实例上的此列表运行实例将如何增长。我无法预测，因为答案可能会根据 OS 资源、框架版本和列表的完整程度而改变。这是一个实现细节。

显然，提供容量会提高性能。如果您不太确定确切的数字，设置一个多余的容量，然后在添加完所有内容后使用 TrimExcess() 可能会起作用。容量只是为了避免必须增加列表的开销。

Answer 2

.net 使用该算法的一种变体，当列表已满时分配一个两倍大的数组，将现有元素复制到其中并释放旧元素，这基本上是扩展初始数组。

事实上，所有提供等效列表的语言都可能这样做，因为没有理由不这样做。

and let's say the number of elements added is N. I'm wondering whether the total complexity would be described as O(N) or O(N^2), when taking into consideration the fact that insertion is "usually" O(1) but will be O(n) "once in a while" when internally the list needs to be copied into a larger array.

这是分摊 O(n) 用于插入 n 个元素和分摊 O(1) 用于插入一个元素。

摊销基本上意味着插入 n 个元素的操作总数平均为 O(n)，即使一个插入可能比另一个执行更多操作，因为必须扩展数组。

要了解这一点，请考虑我在第一段中描述的经典算法。假设我们的容量最初是1。我们将在扩展数组时统计执行了多少操作。当插入第一个元素时，我们有：

操作，因为数组没有扩展

插入第二个元素必须将现有元素复制到新数组中，然后才执行插入。为清楚起见，我们将忽略内存操作引入的常量。所以这是：

操作（复制1个元素，新容量为2）。

当插入第三个元素时，我们有：

操作（复制2个元素，新容量为4）

插入第四个元素时，我们有0次操作，因为我们还有空间。

插入第五个时，我们有：

操作（复制4个元素，新容量为8）

一般来说，当插入第2^k+1个元素时，我们会有：

2^k

操作。

k 可以有多大？ log base 2 of n (log n)，因为这样我们就有足够的空间容纳 n 个元素。

因此所有调整大小操作的复杂度由总和给出：

S = 1 + 2 + 4 + ... + 2^k, k = log n
S = (1 - 2^k) / (1 - 2) // sum of a geometric progression with ratio 2
  = 2^k - 1
  = 2^(log n) - 1
  = n - 1
  = O(n)

所以总复杂度是 O(n) 加上另一个 O(n) 因为我们没有计算实际的插入。但是总共还是O(n)

如果我不指定容量，将 N 个元素插入到 List<T> 中的复杂度顺序是什么？

What is the order of complexity of inserting N elements into a List<T> if I don't specify a capacity?

.net

c#

algorithm

complexity-theory

time-complexity