平成26年度 春期 午前 問19

✓ これが正解エ同じ軸で，高さが変わらない水平な直線（データの個数によらず一定）

解説

衝突が無ければ、件数によらず一か所見るだけです。

設問は、ハッシュ表の理論的な探索時間を示すグラフを選ばせています。図を見る前に、探す手順を数えて計算量を一語で決めてしまうのが確実です。手順は二つしかありません。キーからハッシュ関数で格納先の番地を求め、その番地を一度見る、それだけです。設問が、複数のデータが同じハッシュ値になることはないと断っているので、見た場所には必ず目的のデータが入っています。比べる回数は常に一回で、表の中に何件あるかを一度も数えていません。したがって、十件でも一千万件でも一件あたりの探索時間は変わらず、計算量は一定です。グラフは高さの変わらない水平な直線になります。なお、現実のハッシュ表では同じ値が重なることが起こるため一定にはなりません。理論的なという断りと、重なりが無いという条件がそろってはじめてこの形になります。

ほかの選択肢はなぜ違うのか

• ア縦軸「データ1個当たりの探索時間」，横軸…：件数が増えるほど所要時間が跳ね上がっていく形で、片端から組合せを試すような探し方の姿です。実用になる探索の伸び方ではありません。
• イ同じ軸で，原点付近から右上へまっすぐ伸び…：件数に比例してまっすぐ伸びる形で、先頭から順に一つずつ見ていく探し方の姿です。件数が二倍になれば所要時間も二倍になります。
• ウ同じ軸で，はじめは増えるが右へ行くほど寝…：伸び方がだんだん鈍っていく形で、範囲を半分ずつ狭めていく探し方に近い姿です。緩やかではあっても、高さは最後まで変わり続けます。