【おーだーきほう（びっぐおー）】
オーダー記法（ビッグオー） とは？
最終更新:
💡 データが増えたときの、必要量の増え方を見る
入力の大きさに対し、処理量やメモリ使用量の増え方を漸近的な上限で表す記法。最悪の場合との違い、係数と実行時間の注意を解説します。
📌 このページのポイント
- 時間やメモリなどの必要量を、入力サイズnで表す
- 十分大きいnでの、定数倍までの上限を示す
- 最悪・平均など、どの場合を測るかは別に決める
- 秒数や厳密な倍率は、記法だけでは分からない
ひよこ O(n)は、何を表す？
ペンギン先生 入力サイズをnとして、処理量やメモリ使用量の増え方を表すよ。ビッグオーは、十分大きいnで、ある関数の定数倍以下に収まるという上限の記法なんだ。
ひよこ データが2倍なら、時間も正確に2倍？
ペンギン先生 そうとは限らないよ。例えば2n+5も3n+100もO(n)と表せる。実際の秒数には、実装や実行環境も関係する。正確な倍率を測る道具ではないんだ。
ひよこ 最悪の場合を表す記号？
ペンギン先生 ビッグオー自体が最悪の場合を指定するわけではない。最悪の場合の処理量にも、平均の場合の処理量にも使える。どの場合、どの操作や資源を数えているかを確認しよう。
ひよこ O(1)なら、一回だけ処理する？
ペンギン先生 入力サイズが増えても、上限が定数で抑えられるという意味だよ。操作が一回とは限らない。同じようにO(log n)だけで、入力が二倍なら必ず一ステップだけ増えるとも言えないんだ。
ひよこ じゃあ、何のために使う？
ペンギン先生 大きな入力を扱うとき、必要な処理量がどう増えるかを比較する助けになる。図はnやnの二乗という式の例だよ。実際の速さやメモリの量も、必要に応じて計測して判断しよう。
もっと詳しく知りたい人へ
O(n)の処理をO(n²)とも書ける？
上限の記法なので、n以上の範囲では、線形の量は二乗の上限にも収まります。比較のためには、できるだけ増え方に近い上限を示すことが有用です。
係数は、実際の速さに関係ない？
ビッグオーでは定数の違いをまとめますが、実行時間には影響します。特に小さな入力では、同じ記法でも実測値が異なり得ます。
まとめ：ざっくりこれだけ覚えればOK！
「ビッグオー」って出てきたら「データ量に対する処理量などの増え方を、上限で表す記法」と思えばだいたいOK！
📖 おまけ：英語の意味
「Big O Notation」 ＝ 大きなOを使う記法
💬 数学で使う漸近記法の一つです。処理量などを入力の大きさの関数として考えます。