平均時間/（a-1）ダイナミックアレイ上のWikipediaの記事に

Question

それは（償却挿入時に正常部から離れている）と述べている：

の値この割合はである。 [容量を増加させる定数係数]は、時間 - 空間トレードオフにつながります。挿入操作あたりの平均時間は約a /（a-1）ですが、無駄なセルの数は（a-1）nである。

（a-1）nは無駄な細胞の出所を知ることができますが、平均時間が/（a-1）の理由を誰にでも説明できますか？

Answer 1

n個の要素を挿入する時間をSとします。

• これらのn個の要素では、n個の要素に少なくとも1つの割り当てが必要です。
• これらのn要素では、n/a要素には少なくとも2つの割り当てが必要です。
• これらのn個の要素には、n/a^2個の要素に少なくとも3つの割り当てが必要です。
• ...

したがって/（a-1）要素を挿入する平均複雑です。