応用情報技術者アルゴリズムとモデルの適用条件オリジナル・公式資料照合難易度
動的配列は満杯になると容量を2倍にし、既存要素を全てコピーする。要素を末尾へn回追加するとき、再確保以外の1回の追加を定数時間とする。平均償却計算量はどれか。
A
1回当たりO(n²)
容量倍増のコピー総数は二次には増加しない。
B
どの1回も必ずO(1)
再確保する1回は多数の要素をコピーするため、最悪時間は定数ではない。
C
1回当たりO(1)★ 正解
コピー総数は1+2+4+…でO(n)に収まり、n回の追加全体がO(n)なので平均償却はO(1)になる。
D
1回当たりO(n)
個々の再確保はO(n)になり得るが、全追加を平均した償却計算量ではない。
解説
コピー総数は1+2+4+…でO(n)に収まり、n回の追加全体がO(n)なので平均償却はO(1)になる。
根拠資料・確認情報
対応範囲：2026年度 応用情報技術者試験／シラバスVer.7.2・科目A/B表記
資料確認日：2026-11-02
アプリ内の初回回答データ
回答データを読み込んでいます。