情報処理の問題で、これがよく分からない

質問

相異なるn個のデータが昇順に整列された表がある。この表を1ブロックm個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、目的のデータの存在するブロックを探し出す。次に当該ブロック内を線形探索して目的のデータを探し出す。このときの平均探索回数はどれか。ここで、 m＜nとし、目的のデータは必ず表の中に存在するものとする。

答えは m/2 + n/2m なのですが、

目的のデータが存在したブロックの中での
線形検索の結果でm/2 となるのは分かるのですが、

なぜ、n/2mで目的のブロックを見つけることが
できるのかが分かりません。

例えば、
(1,8,9),(10,13,14),(17,19,20) で
３つずつのブロックに分けて各ブロックの最後尾
の数だけで線形検索を行うってことは、

9,14,20 で　検索するってことで 平均2/3
で見つかることは分かります。

けれど、目的の数値が9,14,20 以外の数字
だったら、目的の数値が
含まれるブロックが見つからない気がするのですが。

例えば目的の数値が、8だったら、
最後尾の数だけで、線形検索しても
該当の数がないので、分からないと思うのです。

どなたか、お馬鹿な私に分かりやすく教えてください。
よろしくお願いします。

回答No.3

he-goshite- · ベストアンサー

この探索法は，たぶん，索引順編成ファイルにおける探索法（の原理）のことを言っているのだと思います。それはともかく，

この例では，全部でｎ個のデータを１ブロックｍ個のデータに分割しますので，ブロック数は（ｎ／ｍ）個です。
で，このような問題で「(平均)探索回数」というのは，「(平均)比較回数」と考えたほうが分かりやすいのではないかと思います。
探索しているデータの含まれるブロックを見つけ出すまでの，ブロック探索の回数は最大で(ｎ／ｍ)回（最小は０回？）なので，平均すると（1/2)×(ｎ/ｍ)回となります。

>目的のデータが存在したブロックの中での
線形検索の結果でm/2 となるのは分かるのですが、

というわけですから，合計の平均探索回数は，
>答えは m/2 + n/2m なのですが、
となります。
これが１個のデータを探索するときの平均線形探索回数（＝目的のデータが含まれるブロックを見つけ出し，さらにブロック内で目的データを見つけ出す までの合計探索回数 の平均値）です。

次の疑問点についてですが，
>例えば目的の数値が、8だったら、
最後尾の数だけで、線形検索しても
該当の数がないので、分からないと思うのです。

線形検索をするときに，たとえばSEAMOONさんのデータ例で，「17」を探しているとすれば，
「17以上」と言う条件で探索します。
そうすると，ブロック探索では，「9」と「14」は適さず「20」が条件に適うものとして第３ブロックが探索結果となります。（実探索(比較)回数＝３）

>9,14,20 で　検索するってことで 平均2/3
で見つかることは分かります。
違います。平均は（1/2)×(9/3)＝３／２回　となります。（個人的意見としては，(1+3)/2＝２が平均回数だと思うのですが）

次に第３ブロック内で同様に「17以上」（今度は「17と等しい」でもいいですが）という条件でブロック内線形探索をすると１回の探索（実回数１回の比較）で目的のデータにたどり着くことになります。

回答No.2

g_express999

いくつか解説ページがありましたのでＵＲＬを貼っておきます。

http://www.jtw.zaq.ne.jp/kayakaya/new/kihon/h12am/h12am_14.htm

http://mt-net.vis.ne.jp/ADFE_mail/0140.htm

お礼

ありがとうございます。
読んでみてもいまいち、理解できません。

なぜ、ｍ／２＋ｎ／２ｍなのでしょう。

ｍ／２ × ｎ／２ｍ なら意味が分かる気が
するのですが。

ん、平均回数を求めるからなのかなぁ。
全回数を求める時はどうなるんだろう

回答No.1

nori_6576

まず、１つ誤解。

＞最後尾の数だけで、線形検索しても
＞該当の数がないので、分からないと思うのです。

昇順に整列されているので、検索対象の数値が最後尾の数値以下なら、そこのブロックに含まれることが分かります。

m/2 + n/2m の n/2m は、n/m ÷ 1/2 かな、と。
つまり、データ数÷ブロック数の半分。

お礼

ふむふむ、ありがとうございます。

補足

>検索対象の数値が最後尾の数値以下なら、

この部分は計算式には表れてこないのでしょうか？

仮に昇順に並んでいないとしたら、
その場合計算式はどうなるのでしょう。

混乱中