応用情報技術者試験 令和5年度 春期 午前 問19

【正解】エ

ハッシュ表では、探索キーをハッシュ関数に入力して、データを格納した位置を表すハッシュ値を求めます。この問題では、複数のデータが同じハッシュ値になる衝突がないため、求めた位置を直接参照できます。表内のデータ数が増えても、ハッシュ値の計算と格納位置へのアクセスという一定の処理だけで探索できます。したがって、データ1個当たりの理論的な探索時間はデータ数に依存せず、計算量はO（1）です。横軸の値が増えても縦軸の値が一定である、水平なグラフのエが該当します。

アの下に凸で急激に増加するグラフは誤りです。これはデータ数の増加に対して探索時間の増加率まで大きくなる、O（nの2乗）などの関係を表す形です。衝突のないハッシュ探索では、このような増加は生じません。

イの直線的に増加するグラフは誤りです。これは先頭から目的のデータを順番に調べる線形探索のO（n）に相当する関係です。

ウの増加しながら次第に傾きが緩やかになるグラフも誤りです。これは二分探索のO（log n）のような、対数的に増加する関係を表します。ハッシュ表の探索時間は対数的にも増加しません。

【ポイント】 衝突のないハッシュ探索の平均及び理論上の探索時間はO（1）です。線形探索はO（n）、整列済みデータに対する二分探索はO（log n）であり、グラフの形と併せて覚えましょう。