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