計算量とO記法（オーダ記法）とは？
計算量とO記法（オーダ記法）とは、アルゴリズムの実行時間や必要な記憶領域が、データ件数nの増加に対してどう増えるかを表したもの。O記法では最も影響の大きい項だけを残し、係数や定数項は無視する。FEでは各アルゴリズムのオーダを問う問題が頻出する。
エンベデッドシステムスペシャリスト試験の過去問では3回出題されています（2017年度〜2021年度）。
けいさんりょうとおーきほう
計算量とO記法（オーダ記法）の意味
アルゴリズムの実行時間や必要な記憶領域が、データ件数nの増加に対してどう増えるかを表したもの。O記法では最も影響の大きい項だけを残し、係数や定数項は無視する。FEでは各アルゴリズムのオーダを問う問題が頻出する。
計算量とO記法（オーダ記法）の具体例
処理時間が3n²+5n+100と表せるなら、nが大きいときはn²の項が支配的なのでO(n²)と書く。データが10倍になると処理時間は約100倍になる。O(log n)なら10倍になっても数回分しか増えない。
計算量とO記法（オーダ記法）は試験でどう引っ掛けられる？
O記法は「増え方の傾向」であり、実際の実行時間の大小を直接示すものではない。nが小さければO(n²)のほうがO(n log n)より速いこともある。また空間計算量（記憶領域）と時間計算量を混同しないこと。係数や定数項は無視するので、O(2n)もO(n+5)もどちらもO(n)と表記される点も見落としやすい。
計算量とO記法（オーダ記法）と関連する用語
計算量とO記法（オーダ記法）が出た過去問
コンピュータの性能評価には、シミュレーションを用いた方法や解析的な方法などがある。シミュレーションを用いた方法の特徴はどれか。
正解：解析的に解が求められないモデルに対しても、数値的に解が求まる。
要点：シミュレーションは解析的に解けないモデルも数値評価できる
解析的な方法は、待ち行列理論などの数式でモデルを閉じた形に解く手法だが、モデルが複雑になると式が立てられなくなる。シミュレーションは実際の動作を計算機上で模擬して統計を取るので、数式で解けないモデルでも数値として結果を得られる。その反面、多数回の試行が必要で計算量は大きく、得られる値には統計的な誤差が伴う。
出典：平成29年度 春期 エンベデッドシステムスペシャリスト試験 am2 問6（IPA）ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
正解：データ1個当たりの探索時間が、表の中のデータの個数に関わらず一定（横一直線）のグラフ
要点：衝突なしのハッシュ表は件数によらず探索時間が一定
ハッシュ表は、キーをハッシュ関数で計算して格納位置を直接求める方式なので、格納されているデータの数を1件ずつ調べる必要がない。衝突が起きない前提であれば、1件を探すのに要する時間は表の中の件数に左右されず一定になる。すなわち計算量はO(1)で、グラフは横軸に対して水平になる。
出典：平成29年度 春期 エンベデッドシステムスペシャリスト試験 am2 問8（IPA）ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
正解：横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数によらず探索時間が一定（水平）のグラフ
要点：衝突がなければハッシュ表の探索時間は件数によらず一定
ハッシュ表では、キーにハッシュ関数を適用して格納位置を直接計算するため、表を順に走査する必要がない。衝突が起きない前提なら、探索はハッシュ値の計算と1回のアクセスで完了するので、データ件数が増えても1件当たりの探索時間は変わらない。計算量でいえばO(1)であり、グラフは横軸に平行な直線になる。
出典：令和3年度 秋期 エンベデッドシステムスペシャリスト試験 am2 問10（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。