動的配列
更新日:
用語解説
動的配列は、実行中に要素数を増減できる配列です。容量が足りなくなると、より大きな領域を確保し直して要素を移します。
■ 試験で押さえるポイント
容量に空きがあれば、末尾への追加はO(1)です。
容量が足りないときは、全要素のコピーが必要なため、その1回はO(n)になります。
容量を2倍ずつ増やすと、追加1回当たりの平均（償却）はO(1)になります。
■ 選択肢での判断ポイント
通常の末尾追加はO(1)、再確保時はO(n)と区別します。
更新日:
動的配列は、実行中に要素数を増減できる配列です。容量が足りなくなると、より大きな領域を確保し直して要素を移します。
■ 試験で押さえるポイント
容量に空きがあれば、末尾への追加はO(1)です。
容量が足りないときは、全要素のコピーが必要なため、その1回はO(n)になります。
容量を2倍ずつ増やすと、追加1回当たりの平均（償却）はO(1)になります。
■ 選択肢での判断ポイント
通常の末尾追加はO(1)、再確保時はO(n)と区別します。