テクノロジ
Big-O記法とは
読み方：ビッグオーきほう
ひとことで言うと：入力サイズに対する計算量の増え方を、支配的な次数で表す漸近記法。
意味をわかりやすく解説
Big-O記法は、入力サイズnが大きくなったときに、アルゴリズムの時間や記憶量がどの程度の速さで増えるかを表す記法です。
定数倍や低次の項を無視し、増加率の支配的な部分に注目します。例えば3n²+10n+5はO(n²)と表します。
具体例
要素数nの配列を先頭から1回調べる線形探索はO(n)、二重ループで全組合せを調べる処理はO(n²)になることがあります。
似た用語との違い
実行時間
Big-Oは特定PCで何秒かかるかではなく、入力サイズに対する増え方を表します。
Ω記法
Big-Oは一般に上界を表す記法として使われます。Ωは下界、Θは同じオーダーの上下界を表します。
覚え方
定数を捨て、一番速く増える項だけ残す。O(1)<O(log n)<O(n)<O(n log n)<O(n²)を意識します。
基本情報技術者試験の試験ポイント
式からオーダーを求める問題、複数アルゴリズムの増加率比較、探索・ソートの代表的な計算量を問われます。
CHECK QUESTION
処理回数が 5n²+3n+100 に比例するとき、Big-O記法ではどう表しますか。
答えを見る
O(n²)です。nが大きいとき支配的なn²項だけに注目し、定数係数は無視します。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。