分期运行时当有大小不等增加动态数组

Question

我有一个动态数组，我不断追加项目上。追加是复杂O(1)。当数组已满，我想增加数组复制过来，这是复杂O(n)。

现在，假设我成长的阵列以不同的速率，当它变满。这些比率是：

ⅰ）的一些常数C

ⅱ）n / 2个

ⅲ）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)

This answer给出了更详细的解释，为什么在比例调整大小动态数组到n（假设它的尺寸调整到n的1或更大的功率）具有恒定摊销成本。