平成24年度 秋期 基本情報技術者試験 午前 問3
テクノロジ／アルゴリズム探索方法とその実行時間のオーダーの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また，実行時間のオーダーがn²であるとは，n個のデータを処理する時間がcn²（cは定数）で抑えられることをいう。 2分探索，線形探索，ハッシュ探索の順にオーダーを示す。 ア：log2 n，n，1 イ：n log2 n，n，log2 n ウ：n log2 n，n²，1 エ：n²，1，n （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成24年度 秋期 基本情報技術者試験 午前 問3
- ア2分探索：log2 n，線形探索：n，ハッシュ探索：1
- イ2分探索：n log2 n，線形探索：n，ハッシュ探索：log2 n
- ウ2分探索：n log2 n，線形探索：n²，ハッシュ探索：1
- エ2分探索：n²，線形探索：1，ハッシュ探索：n
正解：ア
解説
2分探索は整列済みデータを半分ずつ絞り込むためオーダーはlog2 nです。線形探索は先頭から順に調べるためオーダーはnです。ハッシュ探索は衝突がなければ計算したハッシュ値の位置に直接アクセスできるため，オーダーは1（データ数によらず一定）です。
選択肢ごとの解説
- ア正しい。2分探索はlog2 n，線形探索はn，ハッシュ探索は1というオーダーの組合せが適切です。
- イ誤り。2分探索のオーダーをn log2 nとしており，実際の2分探索（log2 n）より大きく見積もっています。
- ウ誤り。線形探索のオーダーをn²，2分探索をn log2 nとしており，いずれも実際のオーダーより大きい値です。
- エ誤り。2分探索をn²，線形探索を1としており，2分探索と線形探索のオーダーが実際と逆転しています。