『アルゴリズムイントロダクション 第3版』（原著: Introduction to Algorithms）で用いられている次の5つの漸近記法について、まとめておく。詳細は第3章（総合版でp.36-）を参照。

• Θ記法（big-theta notation、上界と下界をあたえる、タイトな限界という）
• O記法（big-o notation、上界のみをあたえる、タイトな限界であるとは限らない）
• Ω記法（big-omega notation、下界のみをあたえる、タイトな限界であるとは限らない）
• o記法（little-o notation、タイトな限界ではない上界をあたえる）
• ω記法（little-omega notation、タイトな限界ではない下界をあたえる）

たとえば、

• $2 n^2 = \Theta(n^2)$
• $2 n^2 \ne \Theta(n^3)$
• $2 n^2 \ne \Theta(n)$
• $2 n^2 = O(n^2)$
• $2 n^2 = O(n^3)$
• $2 n^2 = \Omega(n^2)$
• $2 n^2 = \Omega(n)$
• $2 n^2 \ne o(n^2)$
• $2 n^2 = o(n^3)$
• $2 n^2 \ne \omega(n^2)$
• $2 n^2 = \omega(n)$

Θ記法

定義

ある関数 $g(n)$ について、$\Theta(g(n))$ とは、ある正の定数 $c_1, c_2, n_0$ が存在して、すべての $n \ge n_0$ に対して、 $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ を満たすような関数 $f(n)$ の集合である。

説明

Θ記法（big-theta notation）は、漸近的な上界と下界をあたえる。

すなわち、 $f(n)$ が $\Theta(g(n))$ である（属する）とは、 $n$ が十分大きいければ（ $n \ge n_0 \ge 0$ ）、 $f(n)$ が $g(n)$ の定数倍（ $c_1 g(n)$ および $c_2 g(n)$ ）につねに挟まれることを意味する。

$n \ge n_0$ において、 $g(n)$ はつねに $f(n)$ と定数倍の範囲で等しくなるので、Θ記法で与えられる $g(n)$ を特に、漸近的にタイトな限界（asymptotically tight bound）という。

たとえば、 $2 n^2 = \Theta(n^2)$ であるが、 $2 n^2 \ne \Theta(n^3)$　、 $2 n^2 \ne \Theta(n)$ である。

（正確には $2 n^2 \in \Theta(n^2)$ だが、このように略記する。詳しくは「等式および不等式における漸近記法」総合版でp.41-を参照。）

なお、他の文献ではΘ記法の意味でO記法が用いられる場合もある。

O記法

定義

ある関数 $g(n)$ について、$O(g(n))$ とは、ある正の定数 $c, n_0$ が存在して、すべての $n \ge n_0$ に対して、 $0 \le f(n) \le c g(n)$ を満たすような関数 $f(n)$ の集合である。

説明

O記法（big-o notation）は、 漸近的な上界をあたえる。

すなわち $f(n)$ が $O(g(n))$ である（属する）とは、 $n$ が十分大きいければ（ $n \ge n_0 \ge 0$ ）、 $f(n)$ が $g(n)$ の定数倍（ $c g(n)$ ）よりつねに小さくなる（上からおさえられる）ことを意味する。

たとえば、 $2 n^2 = O(n^2)$ であるが、上界しか示さないので、 $2 n^2 = O(n^3)$ も成り立つ。

なお、他の文献ではΘ記法の意味でO記法が用いられる場合もある。

Ω記法

定義

ある関数 $g(n)$ について、$\Omega(g(n))$ とは、ある正の定数 $c, n_0$ が存在して、すべての $n \ge n_0$ に対して、 $0 \le c g(n) \le f(n)$ を満たすような関数 $f(n)$ の集合である。

説明

Ω記法（big-omega notation）は、漸近的な下界をあたえる。

$f(n)$ が $\Omega(g(n))$ である（属する）とは、 $n$ が十分大きいければ（ $n \ge n_0 \ge 0$ ）、 $f(n)$ が $g(n)$ の定数倍（ $c g(n)$ ）よりつねに大きくなる（下からおさえられる）ことを意味する。

たとえば、 $2 n^2 = \Omega(n^2)$ であるが、下界しか示さないので、 $2 n^2 = \Omega(n)$ も成り立つ。

o記法

定義

ある関数 $g(n)$ について、$o(g(n))$ とは、任意の正の定数 $c \gt 0$ に対して、ある正の定数 $n_0 \gt 0$ が存在して、 すべての $n \ge n_0$ に対して $0 \le f(n) \lt c g(n)$ を満たすような関数 $f(n)$ の集合である。

説明

o記法（little-o notation）は、漸近的にタイトな限界ではない、漸近的な上界をあたえる。

すなわち、たとえば $2 n^2 = o(n^3)$ であるが、 $2 n^2 = \Theta(n^2)$ であるため、 $2 n^2 \ne o(n^2)$ となる。

o記法では、 $n$ が大きくなるにつれて、 $f(n)$ は $g(n)$ に対して相対的に無限小に近づくので、

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$

が成立する。

ω記法

定義

ある関数 $g(n)$ について、$\omega(g(n))$ とは、任意の正の定数 $c \gt 0$ に対して、ある正の定数 $n_0 \gt 0$ が存在して、 すべての $n \ge n_0$ に対して $0 \le c g(n) \lt f(n)$ を満たすような関数 $f(n)$ の集合である。

説明

ω記法（little-omega notation）は、漸近的にタイトな限界ではない、漸近的な下界をあたえる。

すなわち、たとえば $2 n^2 = \omega(n)$ であるが、 $2 n^2 = \Theta(n^2)$ であるため、 $2 n^2 \ne \omega(n^2)$ となる。

ω記法では、 $n$ が小さくなるにつれて $f(n)$ は $g(n)$ に対して相対的に無限大に近づくので、

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$$

が成立する。

漸近関係の性質

推移性は、Θ、O、Ω、o、ωのすべてにおいて成り立つ。すなわち、

• $f(n) = \Theta(g(n)) \land g(n) = \Theta(h(n)) \implies f(n) = \Theta(h(n))$
• $f(n) = O(g(n)) \land g(n) = O(h(n)) \implies f(n) = O(h(n))$
• $f(n) = \Omega(g(n)) \land g(n) = \Omega(h(n)) \implies f(n) = \Omega(h(n))$
• $f(n) = o(g(n)) \land g(n) = o(h(n)) \implies f(n) = o(h(n))$
• $f(n) = \omega(g(n)) \land g(n) = \omega(h(n)) \implies f(n) = \omega(h(n))$

反射性は、Θ、O、Ωにおいてのみ成り立つ。すなわち、

• $f(n) = \Theta(f(n))$
• $f(n) = O(f(n))$
• $f(n) = \Omega(f(n))$

対称性は、Θにおいてのみ成り立つ。すなわち、

• $f(n) = \Theta(g(n)) \iff g(n) = \Theta(f(n))$

また、OとΩ、oとωのそれぞれについて転置対称性が成り立つ。すなわち、

• $f(n) = O(g(n)) \iff g(n) = \Omega(f(n))$
• $f(n) = o(g(n)) \iff g(n) = \omega(f(n))$

これらの性質について、実数の同値関係・順序関係と比較すると、

• $\Theta \approx a = b$
• $O \approx a \le b$
• $\Omega \approx a \ge b$
• $o \approx a \lt b$
• $\omega \approx a \gt b$

のような類似性が見出されるが、漸近関係についてはかならずしもどれかひとつが成立するとは限らないことに注意。

参考

• 『アルゴリズムイントロダクション 第3版 総合版』2013年、近代科学社
  • 原著: Introduction to Algorithms
    • Thomas H. Cormen
    • Charles E. Leiserson
    • Ronald L. Rivest
    • Clifford Stein
  • 翻訳:
    • 浅野 哲夫
    • 岩野 和生
    • 梅尾 博司
    • 山下 雅史
    • 和田 幸一
  • ISBN: 978-4764904088