上界 / 下界 / タイトバウンド
アルゴリズムの計算量などに利用する表現。下記の表現のうち、f(n)の最高次項のみ考慮する。
上界(upper bound)
全てのn >= n0に対して、0 <= g(n) <= cf(n)であるような正の定数c, n0が存在するならば関数g(n)は高々オーダーf(n)であるといい、記号O(f(n))で表す。
このとき関数g(n)の上界はO(f(n))
下界(lower bound)
全てのn >= n0に対して、0 <= cf(n) <= g(n)であるような正の定数c, n0が存在するならば関数g(n)は少なくともオーダーf(n)であるといい、記号Ω(f(n))で表す。
このとき関数g(n)の下界はΩ(f(n))
タイトバウンド(tight bound)
全てのn >= n0に対して、0 <= c1f(n) <= g(n) <= c2f(n)であるような正の定数c1, c2, n0が存在するならば関数g(n)は少なくともオーダーf(n)であるといい、記号Θ(f(n))で表す。
このとき関数g(n)のタイトバウンドはΘ(f(n))
