これで完全理解！ランダウの記号（Big-O記法）を基礎から丁寧に解説
目次
ランダウの記号とは
ランダウの記号（Landau’s symbols）は、関数の漸近的な振る舞いを記述するための記法で、主に計算機科学や数学において、アルゴリズムの計算量や関数の極限挙動を簡潔に表現するために使われます。
もっとも有名な記号は Big-O記法（オー記法）で、これは「ある関数が別の関数と同じオーダーで増加するか、より遅く増加する」ことを示します。
Big-O記法（O記法）
Big-O記法は、関数 \( f(n) \) が別の関数 \( g(n) \) によって上から抑えられることを示します。形式的には以下のように定義されます：
ある定数 \( c > 0 \) および \( n_0 \in \mathbb{N} \) が存在して、
$$ \forall n \geq n_0, \quad |f(n)| \leq c \cdot |g(n)| $$
が成り立つとき、次のように書きます：
$$ f(n) = O(g(n)) $$
例1：
\( f(n) = 3n^2 + 2n + 1 \) のとき、
$$ f(n) = O(n^2) $$
これは、3次項や対数項などよりも「最大の項（この場合は \( n^2 \)）」が支配的であるためです。
例2：
\( f(n) = 5n \log n + 20 \) は、
$$ f(n) = O(n \log n) $$
Big-Ω記法（Ω記法）
Big-Ω記法は、関数がある下限を持つことを示します。すなわち、ある程度大きな入力に対して、関数 \( f(n) \) が少なくとも \( g(n) \) のオーダーで成長することを意味します。
形式的には以下のように定義されます：
ある定数 \( c > 0 \)、および \( n_0 \in \mathbb{N} \) が存在して、
$$ \forall n \geq n_0, \quad |f(n)| \geq c \cdot |g(n)| $$
のとき、
$$ f(n) = \Omega(g(n)) $$
例：
\( f(n) = n^3 + n \) は、
$$ f(n) = \Omega(n^3) $$
Big-Θ記法（Θ記法）
Big-Θ記法は、関数が上限・下限の両方を持ち、ある関数 \( g(n) \) と同じオーダーであることを示します。
定義は次の通りです：
定数 \( c_1, c_2 > 0 \)、および \( n_0 \in \mathbb{N} \) が存在して、
$$ \forall n \geq n_0, \quad c_1 \cdot |g(n)| \leq |f(n)| \leq c_2 \cdot |g(n)| $$
のとき、
$$ f(n) = \Theta(g(n)) $$
例：
\( f(n) = 7n^2 + 4n \) のとき、
$$ f(n) = \Theta(n^2) $$
Little-o記法
Little-o記法は、関数 \( f(n) \) が \( g(n) \) よりもはるかに遅く増加する（または減少する）ことを示します。
定義は以下の通りです：
任意の定数 \( \varepsilon > 0 \) に対して、ある \( n_0 \in \mathbb{N} \) が存在して、
$$ \forall n \geq n_0, \quad |f(n)| \leq \varepsilon \cdot |g(n)| $$
のとき、
$$ f(n) = o(g(n)) $$
例：
\( f(n) = n \)、\( g(n) = n^2 \) のとき、
$$ n = o(n^2) $$
Little-ω記法
Little-ω記法は、関数が別の関数よりもずっと早く成長することを示します。
形式的には：
任意の定数 \( c > 0 \) に対して、ある \( n_0 \in \mathbb{N} \) が存在して、
$$ \forall n \geq n_0, \quad |f(n)| \geq c \cdot |g(n)| $$
かつ、
$$ \lim_{n \to \infty} \frac{g(n)}{f(n)} = 0 $$
のとき、
$$ f(n) = \omega(g(n)) $$
例：
\( f(n) = n^2 \), \( g(n) = n \) のとき、
$$ n^2 = \omega(n) $$
各記法の比較とまとめ
| 記法 | 意味 | 関係性 |
|---|---|---|
| O | 上限 | 増加速度は高くても良い |
| Ω | 下限 | 増加速度はそれ以上 |
| Θ | 上下限一致 | ちょうど同じオーダー |
| o | 真の下限 | より遅く増加 |
| ω | 真の上限 | より速く増加 |
実際の応用例
アルゴリズムの計算量
ソートアルゴリズムの比較：
- バブルソート：\( O(n^2) \)
- クイックソート（平均）：\( O(n \log n) \)
- マージソート：\( O(n \log n) \)
関数の極限評価
例えば、
$$ \lim_{n \to \infty} \frac{\log n}{n} = 0 \Rightarrow \log n = o(n) $$
解析学における漸近展開
テイラー展開の余項評価などで、
$$ \sin x = x – \frac{x^3}{6} + o(x^3) $$
のように使われます。
