応用情報技術者 試験情報＆徹底解説

「mは十分に大きく、」とありますが、
n/mは十分大きいと言い切れるのでしょうか？
例えば、m=100、n=500の場合、n/m=5になってしまいます。

言い切れないと思います。
ご指摘のように「nがmの倍数」の条件からは
(n/m)が5の場合も無限大の場合もあり得ます。
計算の最後に十分小さいと判断できた項のみ
近似で除去して、以下のように考えました。

[1]ブロックを特定するまでの平均比較回数
{1+(n/m)}/2

[2]ブロック内のデータを探索するまでの平均比較回数
(1+m)/2

[1]+[2]の平均比較回数
1 + n/(2m) + m/2

1は、m/2が十分大きいので、無視できる。
n/(2m)は、nがmより十分大きい場合に十分大きくなり、無視できない。
近似の結果、n/(2m) + (m/2) になる。

横から失礼します。

解説に
「N個のデータの中から目的のデータを探すときの平均比較回数は(N＋1)／2回です。」
とありますが、これが成り立つのは、N個のデータの中に目的のデータがあるとは限らない場合です。(最小で1回、最大でN回で、その平均)

この問題では、
「目的のデータは必ず表の中に存在するものとする。」
となっていますから、平均比較回数は、最小で1回、最大でN－1回で、N／2です。

そうすると、正解はすんなりとイです。

通りすがりの者さんへ
  ご指摘、ご教示ありがとうございます。理解致しました。
T.S.さんへ
  誤った投稿をしてしまい、申し訳ありませんでした。

通りすがりの者さん
平均比較回数がN/2の時は、Nが十分大きい場合だけでなく、
目的データが必ず存在する場合にも使えるのですね。

勉強になりました。ありがとうございます！

追加の質問があったときに、と思っていましたが、追記します。ちょっと難しいですよ。

目的のデータの存在するブロック内を線形探索するときは、
「目的のデータは必ず表の中に存在する」
わけですから、平均比較回数は、(N＋1)/2ではなく、N/2です。

難しいのは、その前に、各ブロックの最後尾のデータだけを線形探索するときです。

各ブロックの最後尾データの中に目的のデータがあるとは限りません。そうすると、(N＋1)/2の式かというと、そうではなくN/2の式です。

なぜなら、全てのデータが昇順ですから、各ブロックの最後尾データも昇順となり、目的のデータを各ブロックの最後尾データと比較するときは、一致するかどうかではなく、
目的のデータ≦各ブロックの最後尾データ
を順次チェックし、成り立てばそのブロックにあることになるし、最後より一つ前のブロックまで成り立たなければ、最後のブロックにあることになり、最大はN－1回です。

ついでに言えば、問題文の「ここで，mは十分大きく」は、解答を導くのに不要な条件です。

追加のご解説ありがとうございます。
先程の「理解しました」は勘違いだったようです。お恥ずかしいです。

解答を導くにあたって、「全てのデータが昇順であること」および
「目的のデータは必ず表の中に存在する」が重要な条件であること、
最大比較回数の「-1」の理由がやっと理解できました。
ご解説のオウム返しで恐縮ですが、最初の自分の投稿を訂正しました。

目的のデータは各ブロックの最後尾データの中にあるとは限らないが、
いずれかのブロック内の何番目かに必ず存在するので、
目的のデータ≦各ブロックの最後尾データを順次チェックする。
最後より一つ前のブロックまで成り立たなければ、
最後のブロックに存在することは明確なので、
ブロック特定までの比較回数は最大：{(n/m)-1}、最小：1平均：n/(2m)

ブロックが特定できたら
ブロック内で目的のデータと一致するデータを順次探索し、
ブロック内の最後尾より一つ前まで見つからなければ
ブロック内の最後尾に存在することは明確なので、
ブロック内探索の比較回数は最大：(m-1)、最小：1、平均：m/2

よって目的のデータ探索までの平均比較回数はn/(2m)+(m/2)になる。

ぽちさん

完璧です。
せっかくここまで煮詰めましたので、管理人様に解説の見直しを別途依頼します。

この投稿は投稿者により削除されました。(2018.05.04 13:49)

この投稿は投稿者により削除されました。(2018.05.04 11:59)

この投稿は投稿者により削除されました。(2018.05.04 13:49)

すみません。イマイチまとまらなかったので書き直しです。

N-1がそういう意味だとすると、ちょっとトリッキーというかプログラミング？的な発想という感じがしました。
机上の理論では、最後から1つ前に無いことが確定しても、最後を検索して見つかったまでが探索回数なのではと自分は捉えているのですが？（なので最大はN）

また、「mは十分に大きく」についてですが、
最小と最大の平均を取ると、以下のようになると思います。
  ブロックの探索回数： (1＋n/m)÷2＝n/2m＋0.5
    ※スレ主さんの言うとおり、nはmの倍数のためn/2mは十分に大きいとは限らない
  ブロック内の探索回数： (1＋m)÷2＝m/2＋0.5
    ※mは十分に大きいので、こちらは≒m/2などと解釈できる？
  合計：  n/2m＋0.5＋m/2＋0.5＝m/2＋n/2m＋1

合計は、m/2＋n/2m＋1となりますが、mが十分に大きいとすると、
先頭のm/2は十分に大きいと解釈できるので「＋1」なんてどうでもいいでしょっという解釈もあり？

通りすがりの者、改め、助け人です。

最大をNととらえると、合計は、m/2＋n/2m＋1です。

mが十分に大きいとき、1は無視できるとして、n/2mはどうなるでしょう？nはmの倍数ですから、nも十分大きいですが、n/2mはその倍数の半分です。これは、m/2に比べれば無視できるほどで、そうすると、m/2だけが残ることになります。逆に、n/2mを残すなら、1も残すべきです。

整理すると、最大をNととらえるなら、平均比較回数はm/2、または、m/2＋n/2m＋1となり、選択肢にありません。
最大をN－1ととらえるなら、平均比較回数はm/2、または、m/2＋n/2mとなります。
正解がm/2＋n/2mということから、最大はN－1でなくてはならないし、mが十分に大きいという条件はあってはならないということになります。

> 通りすがりの者、改め、助け人さん
やっと通りすぎたという感じでしょうか（笑）

「mが十分に大きい」については、おっしゃるとおりで納得できるほどではありません。
どちらかというと、投げかけて他力本願という感じです。ごめんなさい。

また、最大をNと捉える場合、m/2＋n/2m＋1は確かに選択肢にありませんが、近似値として「m/2＋n/2m」を選択できるかなと思います。（近似値を選択する例はたまにあるので）

最大を「N」か「N-1」と捉えるかについては、他の方の意見も欲しいところです。
正直、このスレッドを見て理解が深まったような状態なので。