dynamic-arrays - 动态数组中每次插入操作的平均时间为 a/(a-1)

Question

在关于动态数组的维基百科文章中，它提到(除了关于摊销插入时间的正常部分):

The value of this proportion a [the constant factor by which we increase the capacity] leads to a time-space tradeoff: the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n.

我可以看到废弃细胞的 (a-1)n 从何而来，但谁能向我解释为什么平均时间是 a/(a-1)？

Answer 1

设S为插入n个元素的时间。

• 在这n个元素中，有n个元素至少花费了1次分配。
• 在这n个元素中，有n/a个元素至少花费了2次分配。
• 在这n个元素中，有n/a^2个元素至少花费了3次分配。
• ...

因此 a/(a-1) 是插入元素的平均复杂度。