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

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

主に漫画、数値計算、幾何計算、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) = 1 + 3x + O(x^2) \quad (x \to 0)

のオーダーの不等号を反転して、誤差項が x^2 のオーダー以上であるということを表したいとします。先の記法を用いると、

f(x) = 1 + 3x + \tau(x)
x^2 = O(\tau(x)) \quad (x \to 0)

のように書くことになるでしょう。これは随分と回りくどい書き方ですし、直感的にも意味を捉えにくいことがあります。やはり逆向きの不等号に相当するオーダー記法はあった方が便利ということもあるのです。

これまでのオーダー記法の反転に対応する記号は、\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^2 のオーダー以上であることを表す記法は、

f(x) = 1 + 3x + \Omega(x^2) \quad (x \to 0)

と1行に収まります。

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

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

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

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

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

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

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

これを用いると、誤差項が x^2 のオーダーに等しいことを表す記法は、

f(x) = 1 + 3x + \Theta(x^2) \quad (x \to 0)

となります。

情報科学における慣例

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

極限と変数の文字

まとめ

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

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