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) 是 arithmetic progression 的总和

附言将数组加倍成本 O(N)