令和5年度春期 ITサービスマネージャ 午前Ⅰ 問6

探索の計算量とグラフ

データ件数と操作回数の関係を読み取るため、計算量の表し方と探索の前提条件を整理する。

この問題で問われていること

理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。

探索の計算量とグラフ

理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。

確認ポイント

• 計算量で使う入力規模nは、探索問題では何の件数を表すか。
• 逐次探索と二分探索について、データ件数を増やすと比較回数がどう変わるかを調べ、グラフに描けるか。
• 実測した処理時間と理論的な操作回数はどう違い、計算量ではどのような定数を省略するか。 キー、ハッシュ値、衝突という用語を調べ、問題文の条件がどの用語に関係するか確認できるか。

正解

エ

解説

添付の公式解答PDFの午前Ⅰ試験の表では，問6の正解は「エ」です。ハッシュ表では，探索対象のキーからハッシュ値を求め，対応する格納位置を調べる。問題の条件ではハッシュ値の衝突がないので，衝突したデータを追加で調べる処理は不要です。このため，理論的な探索時間は表のデータの個数に依存せず一定となり，計算量はO(1)です。横軸が「表の中のデータの個数」，縦軸が「データ1個当たりの探索時間」であることから，水平なグラフが対応する。

添付の公式解答PDFの午前Ⅰ試験の表では，問6の正解は「エ」です。ハッシュ表では，探索対象のキーからハッシュ値を求め，対応する格納位置を調べる。問題の条件ではハッシュ値の衝突がないので，衝突したデータを追加で調べる処理は不要です。このため，理論的な探索時間は表のデータの個数に依存せず一定となり，計算量はO(1)です。横軸が「表の中のデータの個数」，縦軸が「データ1個当たりの探索時間」であることから，水平なグラフが対応する。

選択肢ア

不正解。データの個数が増えるほど，探索時間の増加が急になるグラフである。ハッシュ値の衝突がないハッシュ表の探索時間には当てはまらない。

選択肢イ

不正解。データの個数に応じて探索時間が直線的に増えるグラフである。ハッシュ値の衝突がない場合，データを順に調べる必要はないので，当てはまらない。

選択肢ウ

不正解。データの個数が増えると探索時間も増えるが，その増加が次第に緩やかになるグラフである。ハッシュ値の衝突がない場合の一定の探索時間を表していない。

選択肢エ（正解）

正解。データの個数にかかわらず，データ1個当たりの探索時間が一定である。ハッシュ値の衝突がない場合，ハッシュ値から格納位置を直接特定できるため，このグラフに対応する。

学習のポイント

理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。