平均時間是A /（A-1）

Question

在動態陣列的維基百科文章它提到（除了上攤銷插入時間的正常部）：

的值這個比例a [我們增加容量的常數因子]導致時間 - 空間折衷：每次插入操作的平均時間約爲a /（a-1），而浪費的單元格的數目受上述限制（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）是平均複雜度來插入的元件。