計算量とは？

計算量の意味

入力サイズnが大きくなったときの処理時間や記憶領域の増え方を表す尺度。定数倍や低次の項を無視してO(1)、O(log n)、O(n)、O(n log n)、O(n²)などと表す。

計算量の具体例

2分探索はO(log n)、線形探索はO(n)。衝突のないハッシュ表の探索はデータ件数によらずO(1)。B+木の検索は木の高さに比例するのでO(log n)。

計算量は試験でどう引っ掛けられる？

「平均」と「最悪」で計算量が異なるアルゴリズムがある（クイックソート、ハッシュ表）。どちらを問われているかを読み取る。

計算量と関連する用語

• 整列アルゴリズム
• ハッシュ法

計算量が出た過去問

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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