わかりやすく 空間計算量 とは

答えのほかに使う枠

六つの数からいちばん大きい値を探すとします。答えは結局、数一つですが、たどり着き方は解き方によって違います。ある解き方は、これまでに見たいちばん大きい値をメモ一枚に書いておき、もっと大きい数が出てきたらそこに書き直します。メモは最後まで一枚です。もっと大きい数が出るたびに新しい枠へ書き足す解き方なら、そのぶん枠が増えます。数を大きい順に並べ直すために丸ごと書き写す解き方なら、入力と同じだけ枠が余分に要ります。こうして答えを作るあいだに書きつける一時的な枠が、場所の費用です。入力はどのみち受け取ったものなので費用に数えず、アルゴリズムがその上に広げた枠だけを数えます。

入力（金）は受け取ったものなので費用ではありません。一時枠をつけるを押すと、もっと大きい数が出るたびに新しい枠へ書き足した記録（青）が現れます。費用に数えるのは、この余分な枠だけです。

場所の費用を測るときに入力を除いて余分な枠だけを見るのは、公平に比べるためです。同じ入力を受け取った二つの解き方を比べるなら、それぞれが余分に使った枠だけを数えなければなりません。では、メモ一枚で解く方法がいつもよいのでしょうか。場所を節約すると、どこか別のところで損をしないでしょうか。次は、時間と場所のあいだの取り引きです。

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

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

場所をもっと使うと場所を節約するを交互に押します。表を先に用意した側（青）は場所をたくさん使うかわりに速く、表なしで毎回数える側（金）は場所を節約するかわりに遅くなります。問題は同じで、取り引きが違うだけです。

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

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

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

その場で並べ替えかコピーを作るを選び、並べ替えを実行を押します。その場（金）は同じ枠の中で位置を入れ替えるだけなので余分は0枠、コピー（青）は入力と同じだけ新しい枠を作ります。結果は同じでも、場所の費用が違います。

その場なら余分は0枠、コピーなら入力と同じだけ。答えは同じなのに、場所の費用ははっきり分かれました。ところで、「0枠か、入力と同じだけか」という言い方に聞き覚えはありませんか。前のレッスンで時間を測ったときも、入力が大きくなっても仕事が増えない場合と、入力と同じだけ増える場合を分けました。その見方を、そのまま場所に当てはめられます。次は入力を大きくしながら、余分な場所がどう増えるかを見ます。

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

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

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

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

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

一行にするとこうなります。アルゴリズムは答えを出すあいだ、答えのほかに一時的な枠を使い、その余分な枠が場所の費用です。入力は費用に入れません。場所と時間はよく交換され、表を先に作って場所を多く使えば速くなり、その場で解いて場所を節約すれば遅くなります。余分な場所も入力に応じて増え、いつも一枠ならO(1)、入力と同じだけならO(n)です。だから、よいアルゴリズムを選ぶときは速さだけを見てはいけません。どれだけ速いかと、どれだけ場所を使うかをあわせて見て、はじめてきちんと選べます。メモリが限られた小さな機器では、遅くても場所を節約する解き方が正解になることがよくあります。

四つの段階を順に押して、一行につなげます。答えのほかに使う枠、場所↔時間の交換、その場 vs コピー、場所も入力に応じて（O(1)/O(n)）まで。空間計算量が一枚にまとまります。

これでアルゴリズムを、時間と場所という二つの物差しで一緒に測れるようになりました。同じ答えを出すいくつもの解き方のうち、どんな状況で何を選ぶかを判断する目ができたのです。速さだけでなく場所の費用まではかりにのせてこそ、アルゴリズムをきちんと選んだと言えます。次のレッスンでは、この二つの物差しを手に、実際の問題をもっと賢く解く方法へ一歩進みます。