計算量とO記法（オーダ記法）とは？

計算量と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記法（オーダ記法）が出た過去問

• ヒープソートの説明として、適切なものはどれか。

  正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

  要点：ヒープソートは順序木から最小値を取り出し続ける

  ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問3（IPA）

• 暗号学的ハッシュ関数における原像計算困難性、つまり一方向性の性質はどれか。

  正解：あるハッシュ値が与えられたとき、そのハッシュ値を出力するメッセージを見つけることが計算量的に困難であるという性質

  要点：一方向性＝ハッシュ値から元のメッセージを逆算できない

  原像計算困難性（一方向性）とは、ハッシュ値だけが与えられたときに、そのハッシュ値になる入力メッセージを求めることが計算量的に困難であるという性質をいう。ハッシュ関数は求めるのは容易でも逆算はできないという一方向性を持つため、パスワードの保存などに利用される。

  出典：令和3年度 春期 高度共通_午前I試験 am1 問12（IPA）

• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。

  正解：表の中のデータの個数によらず、データ1個当たりの探索時間が一定（横一直線）のグラフ

  要点：衝突のないハッシュ表の探索はデータ数によらずO(1)

  衝突が起こらない理想的なハッシュ表では、キーからハッシュ関数で格納位置を直接計算できるため、格納されているデータの個数に関係なく一定回数のアクセスで目的のデータに到達できる。すなわち計算量はO(1)であり、グラフは横軸に対して水平な直線になる。

  出典：令和5年度 春期 高度共通_午前I試験 am1 問6（IPA）