c# - 如果不指定容量，将 N 个元素插入 List 的复杂度顺序是什么？

Question

假设我有类似的东西

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

假设添加的元素数量为 N。我想知道在考虑插入“通常”这一事实时，总复杂度是否会被描述为 O(N) 或 O(N^2) O(1) 但当内部需要将列表复制到更大的数组时，“偶尔”会是 O(n)。

Answer 1

.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.

插入 n 个元素的摊销 O(n) 和插入一个元素的摊销 O(1)。

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

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

0

操作，因为数组没有扩展。

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

1

操作(复制1个元素，新容量为2)

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

2 

操作(复制2个元素，新容量为4)

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

插入第五个时，我们有:

4

操作(复制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) 的总和。