ダイナミック配列リサイズの償却解析

Question

動的配列のサイズ変更に関する質問（ArrayList ADTの一部として）が私を困惑させました。

テキストは、要素が配列の最後に追加されるシナリオを設定します。配列がその容量に達すると、そのサイズは倍になります。新しい大きな配列は、古い配列の要素で初期化されます。このプロセスの償却分析は、O（n）の複雑さをもたらす。

は、その後、次の質問が尋ねられる：容量Nのアレイが、代わりに容量の2Nの配列にN個の要素をコピーするいっぱいになると、それらはN/4の配列にコピーされ

追加のセル、すなわち容量のアレイ（N + N/4）。 へのn個の追加シーケンスを実行すると、配列は依然としてO（n）で実行されることを示します。

どのようなヒント、この質問にアプローチする上での助けが大歓迎です。私は、フル・キャパシティのアレイが現在のサイズの倍数ではなく、そのサイズのほんの少しだけサイズが増えているという事実をどう扱うべきか分かりません。

Answer 1

連続コピーはその結果、Kのコピーの後、コピーの総コストは

sum(i=0,K-1){ N(5/4)^i } 

サイズN、N（5/4）、N（5/4）^ 2、...

であるました

その時点で、アレイのサイズはN(5/4)^(K-1)です。

だから残っているすべては言葉で

O([ sum(i=0,K-1){ N(5/4)^i } ]/[ N(5/4)^(K-1) ]) = O(1) . 

が、これはコストを償却される配列要素、あたりのコピーの総コストがあることを示すことです。式が真で表示

は非常に簡単です、そしてロジックはずっと倍増のための同様の関係を示すと同じです：

O([ sum(i=0,K-1){ N(2)^i } ]/[ N(2)^(K-1) ]) 

私はあなたの楽しみを奪うことはありません。