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

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

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

オーダー記法・その1:使用例からの導入

今回は情報科学においてよく用いられる「オーダー記法」について説明します。オーダー記法は、諸量の評価式から重要な部分を抜き出すのに便利な記法であり、情報系分野では基本的な記法として多く用いられます。ただ、見かけによらずその厳密な意味は少々複雑です。また、情報系独特とも言える記法もしばしば見かけます。そこで、今回はそれをやや詳しく扱ってみようということで、このトピックを選択しました。

オーダー記法は、関数が無限大ないし特定の変数値に向かう際の振る舞いを、大雑把かつ簡潔に表現するための記法です。これを「漸近記法」、あるいは、それを広めた人にちなんで「ランダウの記号」ということもあります。*1普通に使われる表現では、「次元が違う」などはオーダー記法の発想と似ています。

オーダー記法は関数の振る舞いを見やすく表現するための単純に便宜的な記法なので、まず使い方に馴染んでから定義を確認する方が理解しやすいと考えて、以下、使用例を見ていきます。

基本的な使い方

オーダー記法の原則は、

  1. 定数倍の違いを無視する
  2. 極限に向かうときの初期の値を無視する

です。

Big-O記法(無限大に向かう場合)

f(x) := 2 x^2 + 3 x を例にとると、無限大に向かう際の振る舞いについては、

x \to +\infty のとき f(x) = O(x^2)

と表されます。また、これを「f(x)x^2 のオーダーである」と読むことがあります。この記法は大文字のOを用いているので、「Big-O記法」と呼ばれます。

それでは、原則から上の式に至る過程を見ていきましょう。

  1. 定数倍の違いを無視しているので、最初の項 2 x^2 の係数は無視されます。
  2. x \to +\infty の極限に対して、初期の x が小さい範囲の値を無視しています。実際、f(x)x = 0 の周囲で x^2 の定数倍を超えてしまうのですが、それは右辺の式には現れていません。
  3. そして、もう一つ現れていないのは、第2項の 3 x です。これは、十分に大きい x に対して  f(x) \leq 4 x^2 が成り立つので、第一、第二の原則に従って無視されたのです。

オーダー記法を用いるにあたっては、無視できる部分は省略して、より簡単な式で表すことが望まれます。なぜなら、オーダーを用いる目的は、関数の大雑把な振る舞いを簡単な式で表すことなので。例えば、上の例は f(x) = O(3 x^2) でも f(x) = O(x^2 + x) でもあるのですが、原則的に余計な係数や項を排除して f(x) = O(x^2) と書くのが適当です。この場合の x^2 のように、オーダーで代表として取る項をしばしば支配項(dominant)と言います。

Big-O記法(特定の数に向かう場合)

別の例として、特定の数に向かっていく場合について見てみます。上に書いた原則はここでも同じです。同じく関数 f(x) := 2 x^2 + 3 x について、x が0に向かうときを考えると、

x \to 0 のとき f(x) = O(x)

となります。

先ほどと違って x がオーダーを支配しているのは、0 の周囲では x^2 の項の方が小さくなるからです。詳しくは、 |x|\leq 1 に対して f(x) \leq 5 x が成り立ちます。

一方で、どんな定数 c > 0 を取っても f(x) \leq c x^2x=0 の周辺では成り立ちません。これは二次不等式を解けば判ることで、f(x) > c x^2 が成り立つ領域は

  • 0 < c < 2 のとき -3/(2-c) < x < 0
  • c = 2 のとき x > 0
  • c > 2 のとき 0 < x < 3/(c-2)

なので、どんな c に対しても x の十分近くに f(x) \leq c x^2 の反例が存在します。よって、x^2 は支配項とはなりません。

small-o記法

さて、Big-O記法があるとすれば、小文字のoを使ったsmall-o記法もあります。今までのBig-O記法はオーダーとして「同じかそれ以下」であることを表していたのに対して、small-o記法はオーダーとして「真に小さい」ことを表します。オーダー記法では定数倍は無視されるので、オーダーがより小さいということは、いかなる定数倍よりも小さいことを意味します。

f(x) := 2 x^2 + 3 x を例にとると、x が無限大に向かう際には、どんな定数 c > 0 をとっても、十分大きい x では g(x) < c x^3 が成り立ちます。厳密に証明することは練習問題ですが、直感的には明らかでしょう。これを

x \to +\infty のとき f(x) = o(x^3)

と表します。また、「f(x)x^3 よりも小さいオーダーである」と読むことがあります。

誤差項の表現

解析学などでよく使われる記法に、誤差項をオーダーで表現するというものがあります。

Big-O記法

Big-O記法における誤差項の表現は、誤差のオーダーを明示するときに用いられることが多いです。例えば、関数 g(x) = 2 x^2 + 3 x + 1 について、

x \to 0 のとき g(x) = 1 + 3 x + O(x^2)

などと書きます。こうすると、1+3x 以外の項が x \to 0 では誤差程度であることを示すことができ、かつ、その誤差のオーダーも一緒に表すことができます。この場合は x \to 0 の極限で考えているので O(x^2) が誤差項となります。

もちろん、x \to +\infty では支配項が 2x^2 となるので、

x \to +\infty のとき g(x) = 2 x^2 + O(x)

などとなります。どこまでを誤差と見なすかはその時々の都合によって決められます。

small-o記法

small-o記法による誤差項の表現は、オーダーの中身よりも漸近的に無視できることに重点を置くときによく用いられます。同じく関数 f(x) について、x が0に向かうときを考えると、

x \to 0 のとき f(x) = 1 + 3 x + o(x)

となります。ここで、o(x)1 + 3x よりも小さいオーダーであるため、誤差として扱われるというわけです。

漸近展開の表現

上のような表現はテイラー展開などの漸近展開を扱うときによく用いられます。例えば、

x \to 0 のとき \sqrt{1 + x} = 1 + \frac{x}{2} + o(x)

などです。この記法が便利なのは、誤差項にどんな定数が掛かっていても簡単に表現できるというところです。

もう少し複雑な例として、h(x) = \sqrt{x^2 + 2x}x \to +\infty における振る舞いを見てみましょう。

h(x) = x \sqrt{1 + 2/x} と変形すると、根号の中の第2項は0に向かうので、テイラー展開を用いて

h(x) = x \left(1 + \frac{1}{x} + o\left( \frac{1}{x} \right) \right) = x + 1 + o(1)

となります。これが意味することは、グラフ y = h(x) は直線 y = x + 1 を漸近線として持つということです。

他の例としては、階乗の近似式として有名なスターリングの公式は

n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n e^{O(1/n)}

と書けます。今度は誤差項が掛け算で効いてきていますね。指数の肩の詳細は、スターリン級数と呼ばれる漸近級数

S_n = \frac{1}{12n} + \frac{1}{288n^2} - \frac{139}{51840 n^3} - \frac{571}{2488320n^4} + \dots

です。実は、この級数は収束しないことが知られています。しかし、漸近級数では高次の項をオーダーの意味で誤差として扱えるので、

S_n = O(1/n)

とできるのです。

スターリングの公式の最後の指数を展開すると

n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n (1 + O(1/n))

また、対数を取ると

\ln n! = \left( n + 1/2 \right) \ln n - n + \ln \sqrt{2 \pi} + O(1/n)

となります。粗い近似式としては

\ln n! = n \ln n - n + O(\ln n)

もよく用いられます。

ちょっと込み入ってきたなぁ…

ここで問題となるのは、上のような式が意味を持つかどうかです。というのも、上の式の o(1/x) などは、特定の関数値を表しているのではなくて、極限と組み合わせて命題を構成するものだからです。一方で、それを値のように扱った方が直感的には見通しがよいという事情もあります。実際、時には 2^{\log n + O(\sqrt{\log n})} のような込み入った表現も見かけます。これも、O(\sqrt{\log n})\sqrt{\log n} の定数倍に収まる関数と見なせば、直感的には理解できる式です。

このように、オーダー記法の微妙さは、直感的な扱いやすさの割に、論理的には少々複雑な命題を表現しているところにあるのです。今回の一連の話の主な目的は、ある程度複雑な場合でも対処できるようにオーダー記法の定義を与えることです。

というわけで、今回の話はここまでとし、ちゃんとした定義を次回に回します。

*1:エドムント・ランダウ(Edmund Landau,1877-1938)解析的整数論の業績で知られる他、多くの教科書を執筆。物理学者のレフ・ランダウ(Lev Landau)とは全くの別人。