space complexity

space complexity（空間計算量）は、プログラムが実行される際にどれだけのメモリ資源を消費するかを定量的に評価するための指標です。これは単にプログラム自体のサイズを指すのではなく、実行時に動的に割り当てられるメモリ量を含めて評価されます。

時間計算量との関係性

アルゴリズムの効率性を評価する際は、time complexity（時間計算量）と併せて検討されることが一般的です。多くの場合、メモリ消費量を抑えようとすると処理時間が長くなり、逆に処理速度を上げるために追加のメモリ（キャッシュや一時的なテーブルなど）を使用するという、トレードオフの関係にあります。例えば、動的計画法では計算時間を短縮するために過去の計算結果を保存するメモリ領域を確保するため、空間計算量が増加します。

評価における注意点

空間計算量を算出する際は、以下の2つの要素を区別して考える必要があります。

固定空間：コード自体や単純な変数など、入力サイズに関わらず常に一定であるメモリ量。
可変空間：再帰呼び出しのスタック領域や、入力データの大きさに応じて動的に確保される配列などのメモリ量。

一般的にspace complexityとして議論されるのは、後者の入力サイズに依存して変化する可変空間の部分であり、これをビッグオー記法を用いて表現します。