ビッグオー記法とは？
びっぐおーきほう
ビッグオー記法とは、アルゴリズムの計算量（時間や空間の増加率）を数学的に表す表記法のことです。
ビッグオー記法（Big O notation）は、アルゴリズムの効率性を評価するために使われる数学的な表記法で、入力サイズnが大きくなったときの処理時間やメモリ使用量の増加の傾向（オーダー）を表します。定数倍の差は無視し、最も支配的な項だけを残すのが特徴です。
代表的なオーダーとその意味は以下のとおりです。
- O(1)：定数時間。入力サイズに関係なく一定（例：配列の添字アクセス）
- O(log n)：対数時間。入力が倍になっても処理は少ししか増えない（例：二分探索）
- O(n)：線形時間。入力に比例して増加（例：線形探索）
- O(n log n)：準線形時間（例：マージソート、クイックソートの平均）
- O(n²)：二乗時間。入力が倍になると処理は4倍に（例：バブルソート）
ビッグオー記法は「最悪ケース」の上限を示すことが多いですが、平均ケースを示すΘ記法（シータ記法）や下限を示すΩ記法（オメガ記法）と合わせて使われることもあります。アルゴリズムを選定したり改善したりする際の共通言語として、ソフトウェアエンジニアにとって必須の概念です。
使い方・例文
「このソートアルゴリズムの時間計算量はO(n log n)なので、バブルソートのO(n²)より大規模データに適している」のように、アルゴリズムの性能比較に用います。
この用語をシェア
最終更新: