x を空の配列のサイズとします。配列がいっぱいになると、長さが k > x の新しい配列が作成されます。古い配列の内容が新しい配列にコピーされ、新しい要素も格納されます。
- 長さ k の配列が k ステップで作成されます
- 要素のコピーには一定の時間がかかります。
質問: 各挿入操作が一定の時間を償却し、n 個の要素の挿入に Θ(n) かかるように、どのように k を選択しますか? 選択した結果、挿入操作ごとに一定の償却時間が得られるという仮定を、償却分析で証明してください。
私の直感では、k = 2*n は良いアイデアだと思いますが、それを証明する方法がわかりません。私は償却分析をまったく理解していなかったと思います。助言がありますか？