はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー！

オーダー記法(O記法，Ω記法，Θ記法)の定義についてのメモ

勉強メモ

はじめに

今回はオーダー記法の定義について書いていきたいと思います。

オーダー記法とは関数の値の発散の速さを漸近的に評価するものです。

実用の仕方というよりはどのように定義をされているかという視点からみていきます。

はじめに
O記法
Ω記法
Θ記法
多項式時間と超多項式時間
付録

O記法

O記法(ビックオー)は関数f(n) の発散のスピードは早くても g(n) と同じくらいという意味で用います。いわゆる関数の上界。

$f(n)\in O(g(n)) \Leftrightarrow ある2つの正定数 n_0 ,cが存在し，全ての整数n \geq n_0 に対して 0 \leq f(n) \leq c g(n)$

例： $3n^3 + n^2 + n + 1 = O(n^3)$ , $3n^3 + n^2 + n + 1 = O(n^4)$
(本来なら $O(n^3)$ は集合なので $3n^3 + n^2 + n + 1 \in O(n^3)$ が正しいですが、=で書くことが多い)

条件を満たすような正定数 $n_0 , c$ を見つけられるかが一番の鍵となります。

簡単な例を用いて、証明をしてみましょう。

関数 $f(n) = n + 1000$ が $O(n)$ に含まれるか？

証明：全ての整数 $n \geq 1000$ に対して， $n + 1000 \leq n + n = 2n$ .
　　　 $\therefore n_0 = 1000 , c = 2$

Ω記法

Ω記法（ビック・オメガ）は関数f(n) の発散のスピードは遅くても g(n) と同じくらいという意味で用います。いわゆる関数の下界。

$f(n)\in Ω(g(n)) \Leftrightarrow ある2つの正定数 n_0 ,cが存在し，全ての整数n \geq n_0 に対して0 \leq c g(n) \leq f(n)$

例： $3n^3 + n^2 + n + 1 = Ω(n^3)$ , $3n^3 + n^2 + n + 1 = Ω(n^2)$

最後の方にある $c g(n) \leq f(n)$ が大切な箇所で，O記法と逆向きになっています。

Θ記法

Θ記法は関数の上界と下界が一致するという意味で用います。

$f(n) \in Θ(g(n)) \Leftrightarrow f(n) \in O(g(n)) かつ f(n) \in Ω(g(n))$

例： $3n^3 + n^2 + n + 1 = Θ(n^3)$

多項式時間と超多項式時間

計算時間が入力サイズnの多項式(定数cに対して $O(n^c)$ )で表されるアルゴリズムを多項式時間アルゴリズムという．

逆に多項式時間アルゴリズムでないものを超多項式時間アルゴリズムと呼びます。

例）多項式時間： $O(1)$ , $O(n^2)$ , $O(nlogn)$
　　超多項式時間： $O(2^n)$ , $n^n$ , $O(n!)$

これらを比べると圧倒的に多項式時間のほうが優秀です。

付録

ざっくりオーダー記法についてまとめましたが、そもそも関数f(n)のnはなにを指しているのでしょうか。

これは一般的に入力サイズ(入力長)を指します。

例えば入力が数字の10だったときは2桁の数ですが、2進数で表したら1010の4bitです。

つまりコンピューター上では２進数で動作するので入力サイズは $log_2(10)$ ( $8 = 2^3 < log_2(10) \leq 16 = 2^4$ )となります。

そこで入力パラメーターにn,Kにおいて $o(nK)$ であったとしても、入力サイズが $n + logk$ ならnに対しては多項式であっても $logK$ に対しては多項式ではなくなってしまいます( $s = logK$ とすると $K = 2^s = 2^{logK})$ 。

このように入力サイズに基づいて考察すると、指数時間であるアルゴリズムを擬多項式時間アルゴリズムといったりします。

入力における数値がすべて一進数で与えられるものとしたときに、その入力サイズの多項式時間で動作するアルゴリズムのことを擬多項式時間アルゴリズムという。