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

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

オーダー記法・その4

今回は新しいオーダー記法を導入します。それらは主に計算量理論において用いられ、他の分野ではあまり見かけることがない(マニアックな)ものです。とはいえ、使うところでは普通に使うので、今後のためにも定義をちゃんと述べておく必要があるでしょう。

これまで扱ってきたオーダー記法とその定義を列挙すると、

  • Big-O記法

f(x) = O(g(x)) \quad (x \to \infty)
\Leftrightarrow
\exists c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f(x)| \leq c |g(x)|

f(x) = O(g(x)) \quad (x \to a)
\Leftrightarrow
\exists c > 0;\;\exists \delta > 0;\;\forall x;\;0 < |x - a| \leq \delta \Rightarrow |f(x)| \leq c |g(x)|

  • small-o記法

f(x) = o(g(x)) \quad (x \to \infty)
\Leftrightarrow
\forall c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f(x)| < c |g(x)|

f(x) = O(g(x)) \quad (x \to a)
\Leftrightarrow
\forall c > 0;\;\exists \delta > 0;\;\forall x;\;0 < |x - a| \leq \delta \Rightarrow |f(x)| < c |g(x)|

でした。

2つの関数 f(x), g(x) に対して、オーダー記法は

  • f(x) = O(g(x))f \leq g
  • f(x) = o(g(x))f < g

のように意味的に不等号に対応させることができました。数学や物理学で使われるオーダー記法はほとんどこれで事足ります。

他のオーダー記法

逆向きの不等号に対応するオーダー記法

これまでの話を踏まえた上で、逆向きの不等号や等号に対応するオーダー記法を定義したいのは人情でしょう。例えば、f(x) = O(g(x)) \; (x \to \infty) とは不等号の向きが逆の

\exists c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f(x)| \geq c |g(x)|

に対しても何らかの記号を当てたいと考えるわけです。ここで式変形をすると、これは

\exists c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |g(x)| \leq (1/c) |g(x)|

とできることから、g(x) = O(f(x)) であることが分かります。

全く同様にして、f(x) = o(g(x)) の不等号を反転させたものは、g(x) = o(f(x)) であることが分かります。

これで万事解決、新しい記号を導入する必要なし、と思えればいいのですが、f(x) のオーダーについて述べているにもかかわらず、f(x) がオーダーの中に入っているのは直接的な記法ではなく、直感的にも意味を捉えにくいことがあります。やはり逆向きの不等号に相当するオーダー記法はあった方が便利ということもあるのです。

これまでのオーダー記法の反転に対応する記号は、\Omega, \omega (オメガ)を使います。*1

それぞれの定義は先のものを流用して

f(x) = \Omega(g(x)) \;\Leftrightarrow\; g(x) = O(f(x))

および

f(x) = \omega(g(x)) \;\Leftrightarrow\; g(x) = o(f(x))

とします。極限は元のオーダー記法で使ったものがそのまま使えます。不等号と対応させると

  • f(x) = \Omega(g(x))f \geq g
  • f(x) = \omega(g(x))f > g

というように考えることができます。

いくつかの例を挙げると、極限を x \to \infty で取るとき、

  • f(x) = x^2 について f(x) = \Omega(x log x)
  • f(x) = 3^x について f(x) = \Omega(2^x)
  • f(x) = 2^x + x^{100} について f(x) = \Omega(2^x)

最初の二つは \Omega\omega に置き換えても成り立ちます。一方、3番目は x \geq 997 において

2^x + x^{100} < 2 \times 2^x

が成り立つので、f(x) = \omega(2^x) とはできません。実際、f(x) = O(2^x) なので両立しません。

等号に対応するオーダー記法

さて、不等号についてはすべて揃ったところで、今度は等号に対応するオーダー記法を導入しましょう。すなわち、

f(x) = O(g(x)) かつ f(x) = \Omega(g(x))

というものです。これを、「f(x)g(x) は等しいオーダーである」と言うことがあります。もちろん、オーダーとして等しいことは関数として等しいことを意味しません。

これについても既に記号があって、

f(x) = \Theta(g(x))

と書きます。\Theta は「シータ」(あるいは「テータ」)と読みます。*2

これを用いると、極限を x \to \infty で取るとき、

f(x) = 2^x + x^{100} について f(x) = \Theta(2^x)

となります。

情報系分野における慣例

情報系分野においては、極限を書かない、オーダーを引き算で使う、といったローカルな慣例が存在します。それは、情報系分野で扱われる関数のほとんどが、非負の数を受け取って非負の数を返すことに由来します。他に、オーダーの別表現や緩いオーダーなどよく使われるものの例を挙げておきます。

極限と変数の文字

数学の少なくない分野において、慣例的に n, m の文字を非負整数に当てることが普通にあります。おそらく n は number の頭文字を取ったもの、m はその隣の文字ということでしょう。一方で直後の p は素数など別の意味を持った数に当てられ、q とセットと見なされることが多いです。

同じく慣例的に、i, j, k を数列などの添字に当てることがよくあります。おそらく i は index の頭文字を取ったもの、残りはその後続ということでしょう。注意すべきは i は虚数単位 (imaginary unit) に用いられる(電気工学では i は基本的に電流を表すため、代わりに後続の j が用いられる)ことですが、使われ方が大きく異なるため混乱のおそれはあまりないと思われます。

情報系分野においては、n, m は概ね入力に含まれる要素数を表します。

計算量を書くときにオーダー記法を用いることの主たる目的は、入力を大きくしていくときに、計算量を支配する最も大きな項に対して、細かい(概ねごちゃごちゃした)部分を隠して、計算量の程度を見やすくすることです。よって極限は n \to \infty 以外に使わないので、いちいち明示することはまずありません。

例えば、

f(n) = O(n \log n)

と書かれている場合、極限は暗黙的に n \to \infty が指定されます。他のオーダーについても同様です。

まとめ

今回までに定義したオーダー記法と不等号との対応関係をまとめると、

  • f(x) = O(g(x))f \leq g
  • f(x) = o(g(x))f < g
  • f(x) = \Omega(g(x))f \geq g
  • f(x) = \omega(g(x))f > g
  • f(x) = \Theta(g(x))f \sim g

となります。(最後のものは本当の等号と区別するために \sim を用いました。)

今回定義した下から3つは、情報科学、特に計算量理論の分野で使われます。というよりは他の分野ではほとんど使われていないようです。というわけで、あまり馴染みのある記号ではないので、今後必要になるときはこのページへの参照をつけることにします。では。

*1:Ω, ω(オメガ)は O-mega つまり「大きいO」という意味です。実は、これまでのオーダー記法で用いてきた O, o は、ローマ字というよりはギリシャ文字のオミクロンだったのです。こちらは O-micron つまり「小さいO」です。オーダーの大小関係を考えれば、これの文字を当てたことが納得できるでしょう。

*2:日本におけるギリシャ文字の読み方は、英語読み(どちらかといえば現代ギリシャ語読みに近い)とドイツ語読み(古典ギリシャ語読みに近い)が混在しています。今は英語読みが主流ですが、昔はドイツ語読みの方が使われたので、現在まで持ち越されているものがあります。