読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

計算量とは

間に挟む形で「計算量」というものを扱う上での心構えなどについて書いておきます。

計算量とは

「計算量」とはその名の通り計算の難しさを測る何らかの数値のことです。あるいは計算にかかるコスト=資源の消費量と言ってもいいでしょう。つまり、ある問題に関して計算量は少なければ少ないほどいいということになります。

では何をもってコストと見做すかというと、それは一概にこれだとは言えるものではありません。むしろ人々が少なくしたいと考えているものがコストであると言う方が適切でしょう。当然それにはいくつもの候補が考えられます。例を挙げると、時間、メモリの消費量、入出力の回数、回路の素子数、消費電力、など、実装のレベルや機械の構成などに依存して様々な要求があり、それごとに計算量の定義があると言っても過言ではありません。例えば、このブログの最初で取り上げた「通信複雑さ」も計算量の一種と言うことができます。

中でも最も代表的な計算量といえば、「時間計算量」をおいて他にはないでしょう。時間計算量とは、ある問題を計算によって解くのに要する時間のことです。時間計算量が小さいということは、すなわち計算が早く終わるということです。ほとんどすべての人はコンピュータを使って何かをするとき、一つ一つの処理が早く済んですぐに次のことができる方が望ましいと考えているはずです。中には処理を遅くしてもメモリの消費を少なくしたいという人もいるでしょうが、それはメモリがよほど小さいかあるいは問題が大きすぎて普通のメモリでは収まらないという場合の話です。*1計算を考えるほとんどの場合において、時間計算量を少なく抑えることは優先度の高い問題であると考えられます。というわけで、今の話で扱っている計算量とは、時間計算量のことです。

時間計算量と基本ステップ

時間計算量と一口に言っても、実は計算をどう考えるかによって定義も値も異なるという問題があります。が、ここを突っ込むと、計算とは何かという哲学的な問題が浮上して面倒なので、とりあえずスルーしておきます。今のところは、計算とは与えられた入力に対して、決められた処理(ステップ)を決められた手続き(プログラム)に従って実行していき、最後に結果を出力する、という一連の流れのことであるとしておきます。

今やっている話では、算術演算、例えば足し算や掛け算などについて、小学校で習った計算方法をもとにしてそれらの計算量を与えることから始めます。まずは10進法での計算から導入して、コンピュータと同じ2進法での計算に進みます。小学校や中学校で習った計算のやり方を思い出しながら、計算量を適切に測ることを考えます。実際には、計算の基本となるステップを決めて、計算を終えるまでに要したステップの数で計算量を測ります。つまり、1ステップの所要時間を単位時間とします。

このようにして定めた時間計算量は、あくまで理論の立場として、抽象化した計算の長さを測るものであることに注意してください。実際、コンピュータに計算をさせたときの所要時間は、実装次第で大きく変わってしまいます。ある場合は1ステップ=1/60秒かもしれませんし、ある場合は1ステップ=1ナノ秒かもしれません。あるいは、ステップの行間にも技術的に必要な処理が挟まっていることは普通にあります。我々が数えるステップというのは、それらの細かい処理を内に含めてしまって、計算の手続きを見やすくしたものであると考えてください。

オーダー記法の利用

計算量を考える多くの場面において、定数倍の違いを無視することがよく行われます。なぜなら、何をもって基本のステップとするかによって、数えられるステップ数も変わってくるためです。

仮にステップの決め方にA(例えばC言語)とB(例えば機械語)の2通りあったとして、Aの1ステップを実行するのにBでは1〜10ステップかかるかもしれません。これでは、ある計算のステップ数を数えるとき、入力の長さを n として、Aの決め方で 3n^2 ステップかかるとすると、Bの決め方では 3n^230n^2 ステップかかるということになります。

どちらかを明示的に指定しないと計算量が決まらないというのでは、普遍的な「計算量」を議論することはできません。しかしながら、どちらも n^2 の部分は共通しているので、これを計算量と見なせば都合がよいということになるのです。さらに言えば、先ほどの1ステップの処理に要する時間の違いも定数倍に含めることができるので、これによって計算量の単位を物理的な意味での時間と見なすことも(理屈の上では)可能になります。

そこで、計算量を理論的に扱う分野では、定数倍の違いを無視するために、オーダー記法(ランダウの記号)を使います。オーダーの復習をするのは本文を一通り読んだ後でも問題ないと思います。世の中には、計算量は杓子定規にオーダーで表すものと思っている方もいるようですが、それを使う理由くらいは知っておいた方がいいでしょう。

計算量をオーダーで表す主な理由は、上で述べた通り、具体的な実装やステップの決め方への依存を抜きにして、抽象的な計算の難しさを議論するためです。あとは見た目上の問題として、煩雑な細かい部分を隠すためというのもあります。計算量はある程度大雑把に測るくらいがちょうどいいのです。

計算量とモデル

計算量を扱う上で忘れてはいけないこととして、計算量はモデルに付随する評価値であるということがあります。

以前に導入した算術計算の計算量は、1桁の演算の回数を数えるというだけの単純なものですが、これを時間計算量として解釈するには「演算は一つ一つ順番に適用される」というモデルの設定が必要です。これを指して直列計算といいます。対義語は並列計算で、同時に複数の演算を行うことができます。例えば、電子回路による計算などが該当します。もし足し算を高度な並列計算が可能なモデルで考える場合、時間という意味で本質的な違いが生じる可能性があります。

すなわち、全体としては同じ回数の演算でも、1単位時間に同時並列で適用することによって、結果を出すまでの時間をずっと短くできるということです。もちろん、以前考えた筆算は繰り上がりのためにそのままでは並列化できないのですが、上手いこと工夫すれば、足し算を効率的に並列化することは可能です。実際、そのように工夫された方法を用いることで、CPUは64ビットの足し算でもビット演算のみで1クロックに収めることができるのです。現実の論理素子は出力が安定するまでに一定時間を要するため、筆算のやり方では全体の出力が定まるまで時間が掛かり過ぎます。

直列計算の計算量を数学的に議論するために用いられる最も基本的なモデルは、チューリング機械(Turing Machine=TM)と呼ばれる仮想的な機械です。現実の計算機で実行できるような計算はすべてTMで実行できるという意味で、TMは最も普遍的な計算機です。そして、我々が普段「時間計算量」と呼んでいるものは、本来はTMのステップ数として定義されるものです。同様に、「空間計算量」もまたTMを用いて定義されます。

ところが、このTMという機械は計算能力の普遍性に反して、非常に原始的な操作しか行えないという問題があります。実際、具体的なアルゴリズムをTMのプログラムにするのは非常に煩雑な操作です。(もし、brainfuckという「非実用的」プログラム言語をご存知ならば、それでアルゴリズムを実装することと大差ないと考えてください。)そのため、アルゴリズムの設計者のほとんどはTMを根底の保証としてだけ用い、計算量の見積もりにおいてもTMを顧みることはありません。計算量は今考えているように適当な基本ステップを数えることで測るのが普通です。

計算の基本ステップを定めることは、それ自体が一つの計算モデルを定めることでもあります。直列計算を一般的に言い表すと、与えられた入力に局所的な処理(基本ステップ)を次々と適用して最終的な結果に持っていく系列のことであり、時間計算量とはその系列の長さのことです。基本ステップの数はこの意味で時間計算量となっているのです。一方で、これがTMにおける時間計算量に定数倍を除いて一致するという希望的観測は、多くの場合自明でないどころか、時には間違っていることさえあります。また、正しくても定数倍の差は埋め様がないのが普通であり、そのために計算量の評価にオーダー記法を使うという事情もあるのです。*2

繰り返すと、計算量はモデルに付随する値です。意味的に同じ類のものでも、モデルが違えば本質的な違いが生じることがあります。そのために、理論の立場では、TMのような普遍的な計算モデルを導入して計算量を定義します。ところが、このようなモデルは具体的なアルゴリズムの計算量を測るには不向きであり、ほとんどの場合、適当な基本ステップを定めて計算量を評価します。そして、以前導入した算術演算の計算量についても、便宜上TMを直接触らないように簡略化したモデルで議論しています。そのことは今後も頭の片隅に置いておいてください。

*1:メモリが十分に足りているにも拘らず、消費を少なくしたいと考えるプログラマは実際いないことはないのですが、それは不要な拘泥と言うべきものです。

*2:TMに帰着しないで考える場合は、可能ならば厳密値で評価すべきという場合もあります。