データ構造とアルゴリズム
可変長配列で、容量が満杯のときに要素を追加すると、2倍の容量の領域を新たに確保して全要素をコピーする。容量1の空の配列に要素を1つずつ1,000個追加したとき、コピーされる要素の総数はいくつか。
- A10
- B1,023
- C499,500
答えと解説を見る
正解：B. 1,023
容量は1、2、4、…、512と満杯になるたびに2倍になり、そのたびにその時点の要素をコピーするので、コピーの総数は 1 + 2 + 4 + … + 512 = 1,023 です。1,000個の追加に対してコピーは要素数の約1倍なので、追加1回あたりの手間は平均すると一定、つまり償却 O(1) になります。容量を1ずつしか増やさないと、コピーは 1 + 2 + … + 999 = 499,500 となり O(n²) です。10は領域を確保し直した回数で、コピーされる要素の数ではありません。
- A. 領域を確保し直した回数(1→2→…→1024の10回)で、コピーした要素の数ではありません。
- B. 正しい。1 + 2 + 4 + … + 512 = 1,023で、追加1回あたり平均約1回のコピーです。
- C. 容量を1ずつ増やした場合のコピーの総数です。