豚吐露＠wiki
問08回答
最終更新：
ohden
-
view
イ
線形探索は、先頭から順に比較を行い検索対象のデータが見つかれば終了する探索方法。
先頭から順番に探索を行うため、i個の配列の場合、平均比較回数はi/2回になる。
先頭から順番に探索を行うため、i個の配列の場合、平均比較回数はi/2回になる。
n個のデータをm個ごとにブロック化しているため、ブロック数はn/m。
ブロックの末尾データのみ参照し検索対象のブロックを特定できるため、ブロックを特定するための平均比較回数はn/2m回。
次にブロック内の線形探索を行うが、ブロックはm個のデータ配列であるため、ブロック内のデータを特定するための平均比較回数はm/2回。
ブロックの末尾データのみ参照し検索対象のブロックを特定できるため、ブロックを特定するための平均比較回数はn/2m回。
次にブロック内の線形探索を行うが、ブロックはm個のデータ配列であるため、ブロック内のデータを特定するための平均比較回数はm/2回。
結果、平均比較回数はn/2m＋m/2回となり、答えはイとなる。
更新日： 2009年11月17日 (火) 17時04分00秒
[Amazon商品]
ASINが有効ではありません。
