空間計算量：場所も費用だ

答え以外にアルゴリズムが余分に使う枠

六つの数の中から一番大きい値を探すとしましょう。答えは、つまるところ数が一つです。でも、それを探す間、ある解き方は小さなメモ一枚に、これまで見た中で一番大きい値を書いておき、より大きい数が出るたびに書き直します。メモはいつも一枚です。別の解き方は、大きい順に並べ直すために、数をまるごともう一度書き写します。こうして答えそのものではなく、答えを作る途中で走り書きする一時的な枠こそが、場所の値段です。入力はもともと受け取ったものなので費用に数えず、その上にアルゴリズムが余分に広げた枠だけを数えます。

入力（金）はただ受け取ったものです。一時枠をつけるを押して、アルゴリズムが答え以外に広げた枠（青）を見ましょう。費用に数えるのは、この余分な枠だけです。

場所を測るときは入力を除き、余分な枠だけを見る、というのがかんじんです。そうしてこそ、同じ入力を受けた二つの解き方を公平に比べられるからです。でも考えてみましょう。メモ一枚で済む解き方が、いつも良いのでしょうか。場所を節約すると、どこか別のところで損をするのではないでしょうか。次で、時間と場所のあいだの取引を見ましょう。

場所を多く使えば速く、節約すれば遅い（交換）

同じ問題でも、場所の使い方しだいで速さが変わります。たとえば、ある値をたびたび問い合わせなければならないとしましょう。一つの方法は、答えを先に全部計算して表に書いておくことです。問うたびに表を一度見れば終わりなので、とても速い。代わりに、その表を入れる場所を別に空けておく必要があります。別の方法は、表を作らず、問うたびに最初から計算し直すことです。場所はほとんどいりませんが、毎回同じ仕事を繰り返すので遅い。場所を渡して時間を稼ぐか、時間を渡して場所を節約するか。これを時間と空間の交換と呼びます。

場所をもっと使うと場所を節約するを押してみましょう。先に表を置く側（青）は場所を多く使って速く、表なしで毎回数える側（金）は場所を節約して遅い。同じ問題、違う取引です。

どちらかが無条件に正しいのではなく、状況に応じて選ぶ、ということを見ました。たびたび問うなら、表を作って場所を渡すのが得で、場所がきついなら、少し遅くても表なしで解くほうがよい。でも、場所を節約するとは具体的に何でしょう。並べ替えのようなありふれた作業で、場所を一枠も余分に使わない解き方と、入力と同じだけもう一組使う解き方を、並べて比べてみましょう。

その場で解く 対 コピーを作る

ばらばらの数を、小さい順に並べるとしましょう。一つの方法は、受け取った枠の中で二つの数の位置を入れ替えながら整えることです。新しい枠を一つも作らず、持っている枠の中で位置だけを変えます。これをその場での並べ替えと呼び、余分な場所はゼロです。別の方法は、入力の数だけ空き枠を新しく用意し、小さいものから選んでその新しい枠に移し入れることです。結果は同じく並んだ列ですが、入力と同じだけ枠を一組余分に使いました。余分な場所が入力の大きさだけかかります。どちらの解き方も正解を出しますが、場所の値段は、ゼロか入力分か、で大きく違います。

その場で並べ替えとコピーを作るを選び、並べ替えを実行を押してみましょう。その場（金）は同じ枠で位置を変えるだけで余分0枠、コピー（青）は新しい枠を入力分だけ作ります。結果は同じでも場所の値段が違います。

その場は余分0枠、コピーは入力分。同じ答えなのに、場所の値段がはっきり分かれましたね。でも、この0枠と入力分という言い方、どこか聞き覚えがありませんか。前回、時間を測るとき、入力が大きくなっても仕事が増えないならどうで、入力に応じて増えるならどう、と話しました。まさにそのレンズを、そのまま場所に当てられます。次で、入力を大きくしながら、余分な場所がどう増えるかを見ましょう。

場所も入力に応じて増える（O(1) か O(n)）

前回のビッグオーは、入力が大きくなるとき時間がどう増えるかを、一文字で要約したものでした。まったく同じ要約を場所にも使います。メモ一枚で一番大きい値を探す解き方は、入力が六つでも百でも、余分な枠がいつも一つです。入力がいくら大きくなっても余分な場所はそのままなので、これを O(1) の空間と呼びます。一方、コピーを作る解き方は、入力が二倍になれば新しい枠も二倍になります。余分な場所が入力に正比例して増えるので、これは O(n) の空間です。かんじんなのは、ビッグオーという同じ道具で、今度は時間ではなく場所が増える形を測る、ということです。

入力を大きくを押して n を大きくしましょう。O(1)（金）は入力が大きくなっても余分な枠がいつも一つ、O(n)（青）は入力と一緒に増えます。ビッグオーをそのまま場所に当てたものです。

同じビッグオー表記ですが、今度は時間ではなく場所に付きました。O(1) なら入力がいくら大きくても余分な場所は小さな定数に縛られ、O(n) なら入力と並んで大きくなります。こうして私たちは、アルゴリズム一つを二つの目で見るようになりました。時間はどれだけかかるか、場所はどれだけ使うか。さあ、この二つを一本の線にまとめましょう。

まとめ：アルゴリズムを見る二つ目の目

全体を一本の線で見ると、こうです。アルゴリズムは答えを出す間、答え以外にも一時的な枠を使います。その余分な枠が場所の値段で、入力は費用から除きます。場所と時間はしばしば交換されます。先に表を作って場所を多く使い速くするか、その場で解いて場所を節約し遅くするか。そして余分な場所も入力に応じて増えます。いつも一枠なら O(1)、入力分なら O(n) です。だから良いアルゴリズムを選ぶとき、速さだけ見てはいけません。どれだけ速いかと、どれだけ場所を使うか、二つの目で一緒に見て、はじめてきちんと選べます。メモリのきつい小さな機器では、遅くても場所を節約する解き方が正解のことが多いのです。

四つのステップを順に押して、一本の線でつなぎましょう。答え以外に使う枠、場所と時間の交換、その場対コピー、そして場所も入力に応じて（O(1)/O(n)）。空間計算量がひと目で整理できます。

これで私たちは、アルゴリズムを時間と場所という二つのものさしで一緒に測れるようになりました。同じ答えを出すいくつかの解き方の中から、どれをどんな状況で選ぶかを見きわめる目ができたのです。速さだけでなく場所の値段までてんびんに載せて、はじめてアルゴリズムを大人らしく選ぶことになります。次回は、この二つのものさしを手に、実際の問題をもっと賢く解く方法へ、もう一歩入っていきます。