动态数组的运行时增加一个常数而不是加倍

Question

我刚刚做完一场考试，其中一个问题总结如下：

给定一个大小为 1000 的空数组，向该数组插入 n 个元素的摊余成本是多少？当数组已满时，我们不会将数组加倍，而是将其增加 1000，并将所有元素复制到新数组中，就像动态表一样。

我的答案是 O(n)，但我完全不确定我的答案。我知道加倍动态表的摊销运行时间是 2，但我找不到关于增长恒定大小的动态表的太多信息。

Answer 1

假设初始大小为 A，增量也为 A，并且我们有 N 个增长步骤。每个步骤都需要 k*Size 基本操作来复制元素（并在需要时清除内存）。

成本 = k * (A + (A+A) + (A+2A) + ... + (A+(N-1) A)) = k (A*N +A*(1 + 2 + 3 +)。 .. + (N-1))) = k * (A*N + A*N*(N-1)/2) = O(N^2 * A) = O(N^2)（假设 A 是持续的）

1 + 2 + 3 +... + (N-1) 是等差数列之和

PS 将数组加倍成本 O(N)