アルゴリズム(全101問中45問目)
No.45解説へ
相異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
出典：平成24年春期 問 9
- m＋nm
- m2＋n2m
- nm
- n2m
広告
解説
線形探索法を2回組み合わせて目的データを探し出すときの平均比較回数を求める問題です。探索するデータ数に注目して考えていきましょう。
線形探索法とは、探索対象データの先頭から1つずつ順番に比較することによって目的のデータを探す方法です。線形探索法では、N個のデータの中から目的のデータを探すときの平均比較回数は (N＋1)／2 回です。
最初は、n個のデータをm個ごとのブロックに分割した最後尾のデータのみを探索します。表のデータは昇順に整列されているので、各ブロック最後尾の並びも昇順になっているはずです。この最後尾データの並びに対して「目的のデータ≦各ブロックの最後尾データ」を順次チェックし、目的のデータが存在するブロックを探します。
この1回目の探索では、データを1つずつチェックしていくので線形探索の考え方を準用できます。探索するデータ数は n／m個 なので、目的のデータが存在するブロックが決定するまでの平均比較回数は、
(n／m＋1)／2 [回]
2回目は、1回目の探索によって見つけたブロック内を線形探索します。探索するデータ数は m個 なので、目的のデータを見つけるまでの平均比較回数は、
(m＋1)／2 [回]
2つの比較回数の合計は、
(n／m＋1)／2 + (m＋1)／2 [回]
となります。ここで、mは十分に大きいという条件が与えられていますが、n／mが十分に大きいとは限りませんので定数項の+1は無視できません。よって、以下のように式を変形します。
(n／m＋1)／2 + (m＋1)／2
＝{(n／m＋1) + (m＋1)}／2
＝(n／m + m + 2)／2
＝n／2m + m／2 + 2／2
＝n／2m + m／2 + 1
"n／2m"は、nがmより十分大きい場合に十分大きくなり無視できない、"+1"はm／2が十分大きいので無視できると考えると、定数項の＋1を除いて n／2m＋m／2。つまり、1回目と2回目の平均比較回数を合わせるとm2＋n2mになります。
※補足
上記の解説ではmが十分に大きいという理由で＋1を除外していますが、線形探索の特性上、目的のデータが必ず存在するならば、最後の1つ前（n－1番目）の要素までの比較で目的のデータが見つからなかった場合、最後の要素が目的のデータであることが確定します。このため最小比較回数を 1回、最大比較回数を n－1回、平均比較回数を n／2回 として考えることもできるでしょう。この考え方だと1回目の平均比較回数が n／2m回、2回目の平均比較回数が m／2回となり、正解の式と一致します。
線形探索法とは、探索対象データの先頭から1つずつ順番に比較することによって目的のデータを探す方法です。線形探索法では、N個のデータの中から目的のデータを探すときの平均比較回数は (N＋1)／2 回です。
最初は、n個のデータをm個ごとのブロックに分割した最後尾のデータのみを探索します。表のデータは昇順に整列されているので、各ブロック最後尾の並びも昇順になっているはずです。この最後尾データの並びに対して「目的のデータ≦各ブロックの最後尾データ」を順次チェックし、目的のデータが存在するブロックを探します。
この1回目の探索では、データを1つずつチェックしていくので線形探索の考え方を準用できます。探索するデータ数は n／m個 なので、目的のデータが存在するブロックが決定するまでの平均比較回数は、
(n／m＋1)／2 [回]
2回目は、1回目の探索によって見つけたブロック内を線形探索します。探索するデータ数は m個 なので、目的のデータを見つけるまでの平均比較回数は、
(m＋1)／2 [回]
2つの比較回数の合計は、
(n／m＋1)／2 + (m＋1)／2 [回]
となります。ここで、mは十分に大きいという条件が与えられていますが、n／mが十分に大きいとは限りませんので定数項の+1は無視できません。よって、以下のように式を変形します。
(n／m＋1)／2 + (m＋1)／2
＝{(n／m＋1) + (m＋1)}／2
＝(n／m + m + 2)／2
＝n／2m + m／2 + 2／2
＝n／2m + m／2 + 1
"n／2m"は、nがmより十分大きい場合に十分大きくなり無視できない、"+1"はm／2が十分大きいので無視できると考えると、定数項の＋1を除いて n／2m＋m／2。つまり、1回目と2回目の平均比較回数を合わせるとm2＋n2mになります。
※補足
上記の解説ではmが十分に大きいという理由で＋1を除外していますが、線形探索の特性上、目的のデータが必ず存在するならば、最後の1つ前（n－1番目）の要素までの比較で目的のデータが見つからなかった場合、最後の要素が目的のデータであることが確定します。このため最小比較回数を 1回、最大比較回数を n－1回、平均比較回数を n／2回 として考えることもできるでしょう。この考え方だと1回目の平均比較回数が n／2m回、2回目の平均比較回数が m／2回となり、正解の式と一致します。
広告