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

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

オーダーのすゝめ

前回の計算量の議論の問題点として、数字の見方(基数)を自由に変えられるとした場合、計算量が一定しないことを最後に述べました。それは例えば計算量がCPUに依存するということであり、計算量を理論的に抽象化して議論する場合の妨げとなります。そこで、計算量理論の世界では、オーダー記法を用いることで違いを吸収することが一般的に行われます。

オーダー記法と算術計算の計算量

前回問題にしたような算術計算におけるワード長への依存性を吸収するには、m,n を変数と見なして、桁数の定数倍の違いに起因する計算量の違いは無視すべきだと考えられます。この目的にうってつけなのが、以前に扱ったオーダー記法です。

以下、足し算を例に議論しますが、引き算、大小比較についても全く同じです。

上界のオーダー

オーダー記法の原則は、

  1. 定数倍の違いを無視する
  2. 極限から離れた初期の値を無視する

です。詳しくは以前書いた記事かWikipediaなどを参照してください。

http://azapen6.hatenablog.com/entry/2013/02/04/214644

これに従うと、足し算の計算量は

T_{+,\ell}(m,n) = O(m)+O(n) = O(\max\{m,n\})

と表すことができます。(オーダーの足し算参照)

ちゃんと定義を書き下すと、

\exists c > 0;\;\exists (m_0,n_0);\;\forall (m,n) \geq (m_0,n_0);\; T_{+,\ell}(m,n) \leq c \max\{m,n\}

となります。(数列のオーダーは特に断りなく m,n \to \infty で考えます。今回のようにものの数を数えるような数列の値は正の数なので、絶対値記号は省略しています。)ここでは c=2 に取れば十分でしょう。

この記法が優れているところは、 入力が同じ数で \ell が自由に変更できる場合でも、計算量を同じと見做すことができることです。異なる \ell_1, \ell_2 に対して、\ell_1 進法で n 桁の数を \ell_2 進法に変換すると、\ell_1, \ell_2 によって決まる数 d=\log_{\ell_2} \ell_1 を用いて、d n 桁(整数に切り上げ)となります。よって、\ell_1 進法での計算量 T_{+,\ell_1}(m,n)=m+n-1 に対して、\ell_2 進法での計算量はおよそ T_{+,\ell_2}(dm, dn)=dm+dn-1 となり、整数への切り上げを考えても、高々 dm+dn+1 に収まります。従って

T_{+,\ell_2}(dm,dn) = O(d \max\{m,n\}) = O(\max\{m,n\})

となり、\ell の読み替えは右辺に影響しないことが判ります。

また、Big-O記法を用いることの書き方に関する利点として、計算量を最良のものに置き換えてもそのまま通用するということがあります。計算量は少ない方がいいので、上のような素朴な方法よりも計算量を小さくできる方法があれば、そちらを用いたいと考えるでしょう。\ell 進法で m,n 桁の数の足し算を行う手続き(アルゴリズム)のうち、(最悪時)計算量を最も小さくできるものの計算量を T^*_{+,\ell}(m,n) とします。これは問題に対して決まる値であって、アルゴリズムによって決まるものよりも普遍的な計算量と考えられます。この T^*_{+,\ell}(m,n) に対して、具体的なアルゴリズムによって決まる T_{+,\ell}(m,n) は一つの上界を与えます。すなわち、

T^*_{+,\ell}(m,n) \leq T_{+,\ell}(m,n)

です。Big-O記法は上界だけを表しているので、

T^*_{+,\ell}(m,n) = O(\max\{m,n\})

はそのまま成り立ちます。つまり、具体的なアルゴリズムに対してBig-O記法で書かれた計算量の上界は、問題に対する最良の計算量にも使えるということです。*1

以上をまとめると、

m,n 桁の足し算の計算量は O(\max\{m,n\}) である

と言うことができます。

このようにオーダー記法は計算量を理論的に扱う上で便利な記法です。理論的には、計算量は問題に対して決まるものであり、それは最良のアルゴリズムの(最悪時)計算量と定義したいところです。また、実装上の問題を考慮しないために、1ステップで処理できるデータ量(足し算で言えば位取りの数の長さ)は、何らかの有限値で上から抑えられているとして、表記上はそれを隠蔽したいものです。オーダー記法はこういった理論上の要請を叶えてくれるからこそ、計算量を表すための記法として普通に用いられるのです。

下界のオーダー

計算量理論においては、下からのオーダー記法、すなわち、Big-Ω 記法やsmall-ω記法、あるいは上下が同じオーダーで抑えられることを表すΘ記法もよく用いられます。なぜなら、計算量理論が目指していることの一つは、具体的な問題に対して計算量の下界を与えることであり、もっと野心的には、上下界を同じオーダーに収めることだからです。上界の評価はアルゴリズムを構成すればよいのである意味やりやすいのですが、下界の評価は多くの場合非常に難しく、オーダーの意味で非自明な下界はほとんど得られていないのが実情です。

さて、足し算の場合は最悪時計算量の下界、つまり、T^*_{+,\ell}(m,n) があるオーダーより小さいときは、必ずある入力に対して計算を間違える、という意味での下からの評価も与えることができます。オーダーで表すと

T^*_{+,\ell}(m,n) = \Omega(\max\{m,n\})

となります。(注:これは T^*_{+,\ell}(m,n) \neq O(\max\{m,n\}) より強い主張です。)

先ほどは計算量の下界を出すことが難しいと言いましたが、これについてはかなり自明なものです。というのも、入力のすべて桁に対して少なくとも1回以上の演算をしないと、ある入力に対して正しい結果を出力することができないためです。上下界が同じオーダーで抑えられたので、

T^*_{+,\ell}(m,n) = \Theta(\max\{m,n\})

と書くことができます。

今回はここまで

今回の話では、前回の最後で述べた位取りの数の読み替えによって計算量に違いが出るという問題に対して、計算量をより抽象的に扱うために、オーダー記法を導入しました。それによって、

m,n 桁の足し算(引き算、大小比較)の計算量は O(\max\{m,n\}) である

という結論を得ました。

次回は掛け算に入ります。掛け算に関しては、実は素朴な筆算よりも計算量のオーダーが良いアルゴリズムが開発されています。それらについても触れつつ、掛け算の計算量について見ることとします。

*1:これは記法の話であって、同じ書き方がそのまま通用するというただそれだけのことです。