【おーきほう】
O記法（ビッグオー記法） とは？
最終更新:
💡 入力が増えたときの、資源の増え方を表す
入力サイズが十分大きくなったとき、計算に必要な時間やメモリなどの増え方の上限を表す記法。実測の秒数や、処理回数そのものを指定する表記ではありません。
📌 このページのポイント
ひよこ O(n)はn回処理するということ？
ペンギン先生 ちょうどn回とは限らないよ。例えば回数が3n＋5でもO(n)で表せる。十分大きいnで、ある固定の定数を掛けたn以下に収まるという意味。図の数表は代表的な関数の値で、実測回数ではないんだ。
ひよこ 最悪の場合だけを表すの？
ペンギン先生 O記法は上界の表記で、最悪の場合という意味を自動で含まないよ。平均の計算量をOで書くこともある。比較するときは、どのケースかと、入力サイズnが件数なのかビット数なのかを合わせよう。
ひよこ 二分探索やハッシュ検索は？
ペンギン先生 ひよこ 二重ループは必ずO(n²)？
ペンギン先生 両方のループがそれぞれn回回るなら、内側の処理回数はn²になる。でも外側がn回、内側が固定の10回なら10nでO(n)。内側が別の入力サイズmに依存するならO(nm)のように、何に依存するかを確認するんだ。
ひよこ O(n)ならO(n log n)より必ず速い？
ペンギン先生 小さな入力では定数や実装の違いが効くので、秒数の順位は断定できないよ。空間計算量にも使えるけど、入力自体を含む全メモリか追加のメモリだけかを明記しよう。実測と増え方の分析は両方役に立つんだ。
もっと詳しく知りたい人へ
O(n)と書けるものは、O(n²)とも書ける？
上界としては書けます。例えば3n＋5はO(n)であり、より緩い上界のO(n²)でもあります。適切に増え方を表すため、通常はできるだけ狭い上界を使います。上下から同じ増え方で挟めるΘ(n)は、O(n)だけより強い説明です。
まとめ：ざっくりこれだけ覚えればOK！
「O記法」って出てきたら「入力が大きくなるときの必要な資源の上界」と思えばだいたいOK！
📖 おまけ：英語の意味
「Big O Notation」 ＝ ビッグオー記法
💬 Oはアルファベットの大文字オーです。数学的な増え方の上界を表し、厳密な増え方を表すΘ記法とは区別します。