高度情報処理技術者試験・情報処理安全確保支援士試験 令和5年度 春期 午前I 問6

【正解】エ

ハッシュ表では、探索キーをハッシュ関数に入力して格納位置を直接求めます。問題の条件では、異なるデータが同じ格納位置に割り当てられる衝突がないため、データ数が増えても、基本的にはハッシュ値の計算と該当位置へのアクセスだけで探索できます。したがって、探索時間はデータ数に依存しない定数時間、すなわちO(1)となり、横軸の値が増えても探索時間が一定であるエのグラフが該当します。

アの、データ数の増加につれて探索時間の増加率まで大きくなるグラフは誤りです。これは指数時間のような、データ数の増加に対して処理時間が急激に増える性質を表しています。

イの、探索時間がデータ数に比例して増えるグラフは誤りです。これはO(n)の線形時間であり、先頭から順に調べる線形探索などの性質です。

ウの、初めは増加するものの次第に増加が緩やかになるグラフは誤りです。これはO(log n)の対数時間を表す典型的な形であり、整列済みデータに対する二分探索などの性質です。

【ポイント】 ハッシュ表の平均探索時間はO(1)ですが、衝突が多い場合は探索時間が長くなります。 計算量のグラフは、O(1)が水平、O(log n)が緩やかな増加、O(n)が直線になることを覚えておきます。