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

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)