Big Ω 記法
Big O 記法では、\(f(x) = O(g(x)) \)は，関数\( g(x) \)が関数\( f(x) \)の上界であることを表しました。
Big Ω 記法では、 \(f(x) = \Omega (g(x)) \)は，関数\( g(x) \)が関数\( f(x) \)の下界であることを表します。
定義
$$ \exists x_0 , \exists C \gt 0 \mbox{ s.t. } x \gt x_0 \Rightarrow |f(x)| \geq C|g(x)| $$
Big Θ 記法
\(f(x) = O(g(x)) \) であり \(f(x) = \Omega (g(x)) \) である場合、つまり関数の上界と下界が一致する場合は、Big Θ 記法を用いて、 \(f(x) = \Theta (g(x)) \) と表します。
定義
$$ \exists x_0 , \exists C_1, C_2 \gt 0 \mbox{ s.t. } x \gt x_0 \Rightarrow C_1|g(x)| \leq |f(x)| \leq C_2|g(x)| $$
具体例
例１
$$ f(n) = 10 n^2 – 100 n + 10 $$
\( f(n) = O(n^2) \) を示す
\( |f(n)| \leq C|g(n)| \) を考える。
\( n \geq 10\) の時\( 10 n^2 \geq 100 n \) なので、絶対値を取って \( |f(n)| = f(n) \)
\( 10 n^2 – 100 n + 10 \leq C \times n^2 \)
\( C = 10 \) で \( n \geq 10\) であれば、 \( 10 n^2 – 100 n + 10 \leq 10 \times n^2 \)
よって、 \( |f(n)| \leq 10 \times n^2 \) であり、\( f(n) = O(n^2) \) \( ∎ \)
\( f(n) = O(n^3) \) を示す
\( |f(n)| \leq C|g(n)| \) を考える。
\(n\) が十分に大きいとき、上と同様に絶対値の記号を取って \( |f(n)| = f(n) \)
\( C = 1 \) で \( n \geq 10\) であれば、\( 10 n^2 – 100 n + 10 \leq 10 \times n^2 \leq n^3\)
よって、 \( f(n) = O(n^3) \) \( ∎ \)
Big O記法は、関数の上界をあらわすので、\( f(n) = O(n^k) \) の時、 \( f(n) = O(n^{k+i}) \) 、ただし\( i \gt 1\) 。
例えば、\(O(n^2)\) であれば、 \(O(n^3)\) 、 \(O(n^4)\)、 \(O(n^5)\)… も OK 。
\( f(n) \neq O(n) \) を示す
\( |f(n)| \leq C|g(n)| \) を考える。
\(n\) が十分に大きいとき、上と同様に絶対値の記号を取って \( |f(n)| = f(n) \)
\( 10 n^2 – 100 n + 10 \leq C \times n \) を示せばよい。
しかし、\(n\)が十分に大きければ、 \( 10 n^2 – 100 n + 10 \geq n^2 \) である。
\(n\)が十分に大きければ、 \( C \times n \lt n^2 \) なので、 \( 10 n^2 – 100 n + 10 \leq C \times n \) は不適。
よって、\( f(n) \neq O(n) \) \( ∎ \)
\( f(n) = \Omega (n^2) \) を示す
\( |f(n)| \geq C|g(n)| \) を考える。
\(n\) が十分に大きいとき、上と同様に絶対値の記号を取って \( |f(n)| = f(n) \)
\( f(n) \geq C \times n^2 \) を示せばよいので、\( 10 n^2 – 100 n + 10 \geq C \times n^2 = 1 \times n^2 \)
\( C = 1\)で、\(n \geq 11.01… \)の時 \( 10 n^2 – 100 n + 10 \geq 1 \times n^2 \)
よって、 \( f(n) = \Omega (n^2) \) \( ∎ \)
\( f(n) = \Theta (n^2) \) を示す
ここまでで、 \( f(n) = O(n^2) \) であり \( f(n) = \Omega (n^2) \) なので、\( f(n) = \Theta (n^2) \) \( ∎ \)