ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。
表の中のデータの個数が増えるにつれて,データ 1 個当たりの探索時間が急激に増加するグラフ
表の中のデータの個数に比例して,データ 1 個当たりの探索時間が増加するグラフ
表の中のデータの個数が増えるにつれて,データ 1 個当たりの探索時間が次第に増加し,一定値に近づくグラフ
表の中のデータの個数にかかわらず,データ 1 個当たりの探索時間が一定であるグラフ
正解は「エ」です。
ハッシュ表では,データのキーからハッシュ関数によって格納位置(アドレス)を直接計算してアクセスします。同じハッシュ値になるデータが存在しない(衝突がない)と仮定しているので,データの個数に関係なく 1 回の計算で目的のデータに到達でき,探索時間はほぼ一定(O(1)O(1)O(1))です。したがって,データ 1 個当たりの探索時間がデータの個数によらず一定となるグラフが適切です。
本文が同じ・似ている問題を表示しています