空間計算量【space complexity】領域計算量

概要

空間計算量（space complexity）とは、コンピュータが特定の手順に従って与えられた問題を解く際に必要とする記憶領域の容量。これが少ないほど、より少ないメモリ容量で問題を解くことができる。

ある問題をコンピュータによって解くには、計算や操作、比較、分岐、繰り返しなど単純な処理を組み合わせたアルゴリズムを定義して、これをコンピュータプログラムの形で実装して実行する。その際、あるアルゴリズムが問題を解くにあたって一度に占有する必要があるメモリなどの記憶装置の容量のことを空間計算量という。

具体的に必要な量は問題の要素数によって変動することが多いため、容量を要素数の式で表したときに支配的な大きさの項を用いて「O（項）」と表記することが多い（オーダー記法）。例えば、空間計算量がO（1）ならば要素数に依らず一定の容量が必要なアルゴリズムであり、O（n²）ならば要素数の2乗に比例して必要なメモリ容量が増える。

一方、問題を解く際に実行しなければならない手順の数（ステップ数）のことは時間計算量という。多くの問題は複数のアルゴリズムで解くことができ、空間計算量も時間計算量も少ないアルゴリズムが優れたアルゴリズムであると言えるが、一般的にはメモリを多く費やせば短時間で解け、長時間かければ少ないメモリ容量で済むという「時間と空間のトレードオフ」の関係が現れることが多い。

(2018.12.24更新)