計算量とオーダ記法とは？
計算量とオーダ記法とは、データ件数 n が増えたときに処理時間や必要記憶がどう増えるかを表す尺度。O(1)、O(log n)、O(n)、O(n log n)、O(n²) の順に増え方が急になる。定数倍や低次の項を無視し、最も影響の大きい項だけで表す。
けいさんりょうとおーだきほう
計算量とオーダ記法の意味
データ件数 n が増えたときに処理時間や必要記憶がどう増えるかを表す尺度。O(1)、O(log n)、O(n)、O(n log n)、O(n²) の順に増え方が急になる。定数倍や低次の項を無視し、最も影響の大きい項だけで表す。
計算量とオーダ記法の具体例
2重ループで全ペアを調べる処理はO(n²)。nが10倍になると時間は約100倍になる。O(n log n)なら約10倍強で済むため、件数が大きいほどアルゴリズムの選択が結果を左右する。
計算量とオーダ記法は試験でどう引っ掛けられる？
オーダは増え方の傾向であって、実際の実行時間そのものではない。件数が小さい範囲では、O(n²)のアルゴリズムがO(n log n)より速いこともある。定数倍を無視している点を忘れないこと。
計算量とオーダ記法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。