ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。
表の中のデータの個数が増えるほど,データ 1 個当たりの探索時間が急激に増加する曲線。
表の中のデータの個数に比例して,データ 1 個当たりの探索時間が増加する直線。
表の中のデータの個数が増えるほどデータ 1 個当たりの探索時間が増加するが,しだいに増加が緩やかになる曲線。
表の中のデータの個数にかかわらず,データ 1 個当たりの探索時間が一定の水平な直線。
正解は「エ」です。
ハッシュ表では,データの格納位置をハッシュ関数で計算して求めます。複数のデータが同じハッシュ値にならない(衝突がない)場合,データの個数にかかわらず 1 回の計算で目的の位置にたどり着けるため,データ 1 個当たりの探索時間はほぼ一定になります。したがって,グラフはデータの個数によらず一定の水平な直線となる エ が正解です。
本文が同じ・似ている問題を表示しています