algorithm - 通过改变大小增加动态数组时的摊销运行时间

Question

我有一个动态数组，我不断地将项目附加到该数组上。追加是复杂性O(1)。当数组变满时，我想扩大数组并将其复制过来，这就是复杂性O(n)。

现在，假设我在阵列变满时以不同的速度增长阵列。这些费率是：

i) 一些常数 C

ii) n/2

iii) n^2

在每种情况下，摊销运行时间是多少？

我相信我能够解决案件i。摊销运行时间将是操作的总成本除以操作的总数。在这种情况下，总成本为C * O(1) + 1 * O(n)，操作总数为C。因此，摊销运行时间为O(n).

但是，在分析剩下的两个案例时，我有点迷茫。在我看来，操作的总数将分别为n/2 + 1和n^2 + 1，但我不太清楚如何计算操作的总成本。

谁能带领我走上正确的道路？

Answer 1

您可以使用与第一种情况类似的分析。

ii.
(n/2 * O(1) + O(n)) / (n/2) = O(1) + O(n)/n = O(1)
iii.
(n^2 * O(1) + O(n)) / (n^2) = O(1) + O(n)/n^2 = O(1)

这个答案给出了一个更详细的解释，为什么一个动态数组按比例调整n（假设它的大小调整为n1 或更大的幂）具有恒定的摊销成本。