平成22年秋期 午前問6

Nasuさん  
(No.1)
[a コード順に格納した探索表] の説明にて、
「データが昇順または降順に整列されている場合は~・・・」と記載がありますが、
問題文を読むと、整列されているのは "データ" ではなく"コード"のようです。
( "データ順" だと意味が変わってくるのでは?と思います)
ですので、下記のように修正されては如何でしょうか?

訂正前:データが昇順または降順に整列~・・・
訂正後:探索要素が昇順または降順に整列~・・・

また、線形探索よりも2分探索の平均計算量が小さくなる理由を記載された方が
より理解が深まるのではないでしょうか。
2018.01.15 19:53
管理人 
(No.2)
ご報告ありがとうございます。
ご提案を踏まえて「ア」の解説を次のように改善いたしました。

「探索表はコード順に整列済みなので、線形探索または2分探索を使用可能です。各探索法の平均探索回数は、線形探索が (N+1)/2 回、2分探索法が [log2N] 回ですので、探索表の要素数が同じならば平均探索回数は2分探索のほうが少なくて済みます。したがってa表には2分探索が適切です。(※[n]はnを超えない最大の整数を表します)」
2018.01.22 17:01

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop