配列の倍増とは？データ構造における動的配列の拡張方法と計算量を解説

プログラミングでは、動的メモリ確保（dynamic memory allocation）を利用して配列を作成することがあります。動的に確保された配列は、適切な手順を踏むことで、後からサイズを2倍に拡張できます。これを「配列の倍増（array doubling）」と呼びます。

配列の倍増のイメージ

たとえば、初期サイズが5の配列を考えてみましょう。

倍増前の配列（サイズ5）

配列を倍増させると、サイズは次のように10になります。

倍増後の配列（サイズ10）

配列を倍増させる手順

サイズnの配列arr（arr[0…n-1]）のサイズを倍増させるには、以下の手順を実行します。

1. 新しいサイズm（通常は2n）の配列を新たに作成する
2. 旧配列arrから新しい配列へ、n個の要素をすべてコピーする
3. arrが新しい配列を指すように参照先を変更する（旧配列は不要になるため解放する）

計算量の分析

サイズmの配列を新規作成する際には、デフォルト値による初期化が行われるため、θ(m)の時間がかかります。さらに、旧配列から新配列への要素コピーには、追加でθ(n)の時間が必要です。したがって、1回の倍増操作全体にかかる時間はθ(m + n)となります。

この操作は配列が満杯になったタイミングでのみ発生し、通常はm = 2nであるため、計算量はθ(2n + n) = θ(3n)、すなわちθ(n)に相当します。

償却解析（Amortized Analysis）による評価

単体で見るとθ(n)という操作は決して安くなく、「高価な操作」とみなされます。しかし重要なのは、このコストがその後のn回の挿入処理にわたって償却されるという点です。n回の反復にコストを分散させると、1回あたりの追加コストはわずかθ(1)に収まります。

このことから、配列のサイズを「定数倍」で拡張する戦略は、漸近的な計算量に悪影響を与えないことが分かります。ちなみに、もしサイズを固定量（例：+10）ずつ増やす方式にすると、頻繁にコピーが発生し、1回の挿入あたりの償却計算量がO(n)まで悪化してしまいます。定数倍による拡張こそが効率的なのです。

実際、C++のstd::vectorやJavaのArrayListなど、多くのプログラミング言語に標準搭載されている可変長配列（動的配列）は、この倍増戦略を採用しています。