テクノロジ系出題頻度 3/3
O記法
おーきほう
定義
アルゴリズムの計算量を入力サイズnに対する上限で表す漸近表記法。
詳細解説
ビッグオー記法とも呼ばれ、f(n)=O(g(n)) は十分大きいnでf(n)≤c·g(n)となる定数cが存在することを意味する。定数倍と低次の項を無視し最も支配的な項のみで評価する。代表例：定数O(1)、対数O(log n)、線形O(n)、線形対数O(n log n)、二次O(n²)、指数O(2^n)、階乗O(n!)。Ω記法は下限、Θ記法は上下両方をタイトに評価する。性能比較やスケーラビリティ分析の標準的指標。
「O記法」が出る問題
関連用語
よくある質問
Q. O記法とは何ですか？
A. アルゴリズムの計算量を入力サイズnに対する上限で表す漸近表記法。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。