Big-O記法とは？

詳細解説

Big-O記法（ランダウ記法）は、アルゴリズムの計算量（時間計算量・空間計算量）をデータ件数nが大きくなったとき、処理ステップ数がどの関数オーダーで増加するかを示す表記法です。定数倍・低次項は無視し、最も影響が大きい項だけを残します。代表的な計算量の例：O(1)は定数時間（データ数に関係なく一定、例：配列の先頭要素へのアクセス）、O(log n)は対数時間（二分探索）、O(n)は線形時間（線形探索）、O(n log n)は準線形時間（マージソート・クイックソート平均）、O(n²)は二乗時間（バブルソート・選択ソートの最悪）、O(2ⁿ)は指数時間（全探索・ナップサック問題の素朴解）。FE試験では各ソート・探索アルゴリズムの計算量を問う問題が頻出です。「なぜO(n log n)のソートが実用的で、O(n²)が非実用的か」を直感的に理解するには、n=1,000の場合でO(n²)=1,000,000回 vs O(n log n)≒10,000回の差で考えると明快です。

FE試験での出題ポイント

• 1O(1)定数・O(log n)対数・O(n)線形・O(n²)二乗の各意味
• 2代表的アルゴリズムとその計算量の対応（線形探索O(n)、二分探索O(log n)、バブルソートO(n²)）
• 3最悪ケース・平均ケースの区別（クイックソートは平均O(n log n)、最悪O(n²)）

関連用語