== 空間計算量

プログラムで問題を処理するとき、条件分岐$italic("if")$や繰り返し$italic("for")$を組み合わせることが多々ある。
問題が解けるまでに要する手順（ステップ）の数を時間計算量といい、かたや問題が解けるまでに必要なメモリサイズを空間計算量という。
空間計算量も時間計算量も少ないアルゴリズムが優れたアルゴリズムであるが、一般的にはメモリを多く費やせば短時間で解け、長時間かければ少ないメモリ容量で済むという「時間と空間のトレードオフ」の関係がある。

同じ問題に対して、複数のアルゴリズムが存在している中、解決したい問題のデータ量が増大しても計算量が膨大に膨れ上がらないアルゴリズムは優秀といえる。

=== ランダウ記法

ランダウ記法$cal(O)()$は、アルゴリズムの時間計算量や空間計算量を大まかに評価するために使われる。
アルゴリズムが入力サイズに対してどの程度の計算時間やメモリを必要とするかを表す。
