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

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

オーダー記法・その2:基本的な定義

それでは、前回の話を踏まえて、オーダー記法を厳密に定義しましょう。

今回は、最も基本的な場合として、

x \to \infty のとき f(x) = O(g(x))

のように、右辺に一つのオーダーだけがある場合を扱います。これは、今後出てくるすべての派生的な記法の大元です。そのために、(筆者ができる範囲で)論理的な破綻が起こらないように注意して話を進めます。

オーダー記法の実用面では、前回の話のように、かなり大雑把で時に乱暴に使われるのが普通です。そもそも、存在意義が関数の極限での振る舞いを大雑把かつ簡潔に表すことなので、あまり複雑なことは考えたくないのです。オーダーの使い方は習うより慣れろというのが本音というわけです。

しかし一方で、オーダー記法が論理的は意外と複雑なことを表しているというジレンマがあります。今回以降の話ではまさにその複雑なところに突撃するわけです。直感的に理解しやすいことが論理的に単純であることを意味しないというのは、世の中ではよくあることです。オーダーを定義に従ってちゃんと扱おうとすると、そのジレンマに阻まれて、しばしば直感を見失いがちになることがあります。

以降では、例でオーダーに対して抱いた直感を常に念頭に置いて、定義の意味を考えてください。あれを数学的に欠陥のないものにすることが、定義をちゃんとすることの目的なので。くれぐれも前後を取り違えてはいけません。

それでは、定義を始めましょう。

Big-O記法

まずはBig-O記法から定義します。

実関数 f(x)g(x) に対して、

f(x) = O(g(x))

と書くとき、これが意味するところは、次のようになります。

x について考えている極限に関して、極限の十分先では
f(x) の大きさが g(x) の定数倍に収まる。

上から引数を取り出すと、オーダー記法とは、

  1. 注目する関数 f(x)
  2. 比較する関数 g(x)
  3. 考える極限

の3つを引数とする命題です。f(x) = O(g(x)) にはまだ極限が指定されていないので、これだけでは意味を持ちません。以降では x を実数として考えますが、その場合にあり得る極限の形としては、

x \to +\inftyx \to -\infty
実数 a に対して x \to ax \to a+0x \to a - 0

がの5つがあります。

もし、x自然数に限られるならば、意味のある極限は

x \to +\infty

だけでしょう。このような場合は、極限の指定を文脈から明らかとして明示しないこともあります。今回扱うのは実数上の極限なので、ちゃんと全部の場合で極限を明示します。

実数上の極限5種類のうち、 x \to +\inftyx \to a の2つが特に重要です。他の極限はこれらの派生で考えられます。一応、極限を統一して扱う枠組みはあるのですが、今回のような具体的な場合を扱うには特に便利ということもありません。というわけで、以下では、 x \to +\inftyx \to a の2つの場合におけるオーダー記法の定義を中心に進めることにします。

x \to +\infty の場合

このときは、

「極限の十分先」=「x が十分大きい」

という意味に取ります。よって、

x \to \infty のとき f(x) = O(g(x))

を言葉で表現すると、

「十分大きい実数 x に対して f(x) の大きさが g(x) の定数倍に収まる」

となります。ここで、f(x) の「大きさ」とは、絶対値 |f(x)| のことを言っているとします。*1比較対象の g(x) についても、非負関数でないときのことを考えて、とりあえず絶対値をつけます。(実際はそうしなければならないような g(x) を取ることはしないものですが。)

過去の記事によれば、「十分大きい実数 x に対して」とは、「ある実数 x_0 が存在して、任意の x \geq x_0 に対して」という意味でした。これを元に定義を書き下すと、次のようになります。

定義: x \to \infty のとき f(x) = O(g(x)) とは、ある実数 c > 0 および x_0 > 0 が存在して、任意の x \geq x_0 に対して |f(x)| \leq c |g(x)| を満たすことを言う。

これを記号的に書くと、

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)|

となります。ちなみに、括弧の中の x \to \infty を言葉でつなぐときに用いる接続詞は as です。(この場合は as x goes to infinity などと言います。)以後の場合も同じです。

オーダーの定義では条件付き量化子を用いると便利ですが、一部解除すると

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

となります。文献によってはこの形で定義されていることもありますが、論理的には等価であり、齟齬はありません。

以上で x \to +\infty の場合のBig-O記法の定義を終えます。もう一つ、上極限を用いた定義もあるのですが、それはまた後ほど見ることにします。

ちなみに、x \to -\infty の極限で考えるときは、x の正負を反転して、「十分大きい -x に対して」から「ある x_0 < 0 が存在して、任意の x \leq x_0 に対して」とします。

x \to a の場合

実数 a について x \to a の極限でオーダーを考える場合は、

「極限の十分先」=「xa の距離がある値以内に収まる」

という意味に取ります。よって、

x \to a のとき f(x) = O(g(x))

を言葉で表すと、

a から十分近い距離にある実数 x に対して f(x) の大きさが g(x) の定数倍に収まる」

となります。ただし、ちょうど x = a で関数が定義されている必要はないので、それは除きます。

ax の距離が |x - a| で与えられることを考えると、「a から十分近い距離にある x に対して」は、

「ある実数 \delta > 0 が存在して、任意の実数 x0 < |x - a| \leq \delta にあるものに対して」

と表現できます。これは、条件付き量化子の言い換えより

「ある実数 \delta > 0 が存在して、任意の実数 x に対して、0 < |x - a| \leq \delta ならば」

と書けます。以上から定義を書き下すと、次のようになります。

定義: 実数 a に関して、x \to a のとき f(x) = O(g(x)) とは、ある実数 c > 0 および \delta > 0 が存在して、任意の実数 x に対して、 0 < |x - a| \leq \delta ならば |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)|

となります。

以上で x \to a の場合のBig-O記法の定義を終えます。

少し変形すると、考える極限として x \to a + 0x \to a - 0 を取ることもできます。それには、上の定義における、0 < |x - a| \leq \delta を前者では 0 < x - a \leq \delta に、後者では 0 < -(x - a) \leq \delta にそれぞれ置き換えればいいだけです。

これを用いると、無限大の極限で考える場合については

f(x) = O(g(x)) \quad (x \to \pm \infty)
\Leftrightarrow
f(1/x) = O(g(1/x)) \quad (x \to \pm 0)
(複号同順)

と表現することができます。

不等号との対応

ところで、以上の定義より明らかに、f(x) = O(g(x)) ならば、g(x) \leq h(x) なる関数 h(x) に関して f(x) = O(h(x))(同じ極限で)も成り立ちます。具体例では、f(x) = 2 x^2 + 3x + 1 に対しては f(x) = O(x^2) に限らず f(x) = O(x^3) も成り立ちます。

もう一つ、f(x) = O(f(x)) は常に成り立ちます。

この意味で、Big-O記法 f(x) = O(g(x)) は関数同士の不等号 f \leq g のような意味を持つと考えることができます。

否定

それでは、f(x) = O(g(x)) でないとはどういうことでしょうか。等号に合わせて f(x) = O(g(x)) の否定を f(x) \neq O(g(x)) と書くことにします。記号の上では等号を否定していますが、実際には命題として否定を取っていることに注意してください。これを論理記号で書き下すには、ド・モルガンの法則を使えば記号的に処理できます。例えば、

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

となります。試しに f(x) = x^2 に対して f(x) \neq O(x) \; (x \to \infty) であることを証明してみましょう。

c, x_0 > 0 を任意に固定して、x_1 = \max{c, x_0} + 1 \geq x_0 と置くと、x_1^2 \geq (c + 1) x_1 > c x_1 が成り立ちます。これは、上で書き下した論理式で g(x) = x と置いた場合に同じです。よって f(x) \neq O(x)\;(x \to \infty) が示されました。

もう少し複雑な例としては、x が整数のとき f(x) = x^2x が整数でないとき f(x) = x で定義される関数に対しても f(x) \neq O(x) であることを示すことができます。この関数はほとんどすべての x に対して f(x) = O(x) ですが、x が整数のところを含めると f(x) \neq O(x) となってしまうのです。証明は上とほとんど同じで、c, x_0 を正の整数とするだけです。

これでBig-O記法の基本的な部分については十分でしょう。

small-o記法

次に、small-o記法の定義に入ります。

実関数 f(x)g(x) に対して、

f(x) = o(g(x))

と書くとき、これが意味するところは、

x について考えている極限に関して、極限の十分先では
f(x) の大きさが g(x) の定数倍よりも真に小さい。

ということです。Big-O記法が不等号 \leq に対応すると考えるならば、small-o記法は真の不等号 < に対応すると考えられます。ここでもやはり、その定義は考えている極限によって

x \to +\infty の場合

このときは、極限に近いことをBig-O記法のときと同じに考えて、「十分大きい実数 x に対して f(x) の大きさが g(x) の定数倍よりも真に小さい」という意味にとります。

ここで「定数倍よりも真に小さい」とは、どのような定数 c > 0 を持ってきても、f(x) < c g(x) となるということです。これを元に定義を書き下すと、次のようになります。

定義: x \to \infty のとき f(x) = o(g(x)) とは、任意の実数 c > 0 に対して、ある実数 x_0 > 0 が存在して、任意の x \geq x_0 に対して |f(x)| < c |g(x)| を満たすことを言う。

これを記号的に書くと、

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)|

となります。

Big-O記法との重要な違いは、最初の \exists\forall になっていることです。比較してみると、

\exists c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f(x)| \leq c |g(x)|(Big-O)
\forall c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f(x)| < c |g(x)|(small-o)

で確かに最初の量化子が入れ替わっています。これがBig-O記法とsmall-o記法の本質的な違いです。

他には、最後の不等号 \leq< に置き換わっています。ただ、これはそこまで本質的ではありません。ただ、small-o記法は「オーダーとして真に小さい」ことを表したいので、どんな関数 f(x) に対しても f(x) = o(f(x)) となってはいけないということです。もし不等号を \leq にすると、f(x) \equiv 0(すべての x に対して f(x) = 0)のときに f(x) = o(f(x)) となる例外が発生してしまいます。最後の不等号を < にしたのは、そのような例外を防ぐための措置です。もっとも、「真に小さい」ことを表すのに < を使うのは自然でしょう。

もう一度繰り返すと、Big-O記法における最初の量化子 \exists\forall に置き換え、あとは不等号を真の不等号に置き換えたものがsmall-o記法の定義となります。

x \to a の場合

極限の近いところの取り方に関してはBig-O記法の場合と同じなので、あとは最初の量化子と最後の不等号を上と同様に置き換えるだけで、こちらの場合のsmall-o記法の定義が得られます。

定義: 実数 a に関して、x \to a のとき f(x) = O(g(x)) とは、任意の実数 c > 0 に対して、ある実数 \delta > 0 が存在して、任意の実数 x に対して、 0 < |x - a| \leq \delta ならば |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)|

となります。

以上で見た通り、最初の量化子の違いを除けば、それ以外の部分はBig-O記法と全く同様です。他の極限を考える場合もそれ以外で注意すべきところはありません。

不等号との対応

以上の定義より明らかに、f(x) = o(g(x)) ならば、g(x) \leq h(x) なる関数 h(x) に関して f(x) = o(h(x)) も成り立ちます。また、f(x) = o(g(x)) ならば f(x) = O(g(x)) が成り立ちます。なぜなら、\forall c > 0 に関して c を1つ選ぶことを考えると、自動的に \exists c > 0 となるためです。

一方で、不等号の置き換えに関して述べた通り、f(x) = o(f(x)) は成り立ちません。

この意味で、small-O記法 f(x) = o(g(x)) は関数同士の不等号 f < g のような意味を持つと考えることができます。

否定

否定に関してもBig-O記法のときと同様に、f(x) = o(g(x)) の否定を f(x) \neq o(g(x)) と書きます。例えば、

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

となります。先ほどのBig-O記法とsmall-o記法の関係の対偶をとれば、f(x) \neq O(g(x)) ならば f(x) \neq o(g(x)) が成り立つことが分かります。

small-o記法の基本的な部分は以上です。

今回はここまで

今回は、オーダー記法の中で広く用いられるBig-O記法とsmall-o記法について、使用例と基本的な定義を述べました。しかし、実際にはもっと複雑な使われ方をすることも多く、基本的な定義だけではカバーできていないことがいくつもあります。例えば、例に出した誤差の表現で

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

のように書いたとき、この式の意味は上で説明した定義には含まれていません。そこは普段は直感で埋められているところなのです。例えば、誤差項 O(x^2) は「x^2 のオーダーの微小量」などと言われることがあります。その厳密な意味は推して測るべしというのが大方の態度なのです。

とはいえ、情報科学においては時に複雑な使われ方をするオーダー記法を、そのような態度で扱うのは少々危ないところがあると思います。この記事を書いた理由はそこにあるのです。また、条件付き量化子や「十分大きい」などの表現の実用例としても適当な話題だと思います。むしろ、オーダー記法を導入するために前の記事を書いたところがあります。

次回はオーダー記法のやや複雑な使用例について述べたいと思います。では。

*1:一般的にはノルム