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

元・通りすがりの者です。同姓の方が登場されましたので、これを機会に改名します。

管理人様

H30春期午前問6について[1145]
でおわかりのように、現在の解説では不十分な点があります。
「全てのデータが昇順であること」および「目的のデータは必ず表の中に存在する」が重要な条件であること、「mは十分大きいこと」は解答を導くのに無関係であることを考慮して、解説を見直していただけませんか？
よろしくお願いします。

掲示板[1145]の投稿について拝読いたしました。
解説の誤りを訂正しつつ、内容を整理し、ブラッシュアップを行いたいと思います。

解説の更新作業に着手するまでに数日を要してしまうかもしれませんが、少しだけお待ちいただければ幸いです。

線形探索法における平均比較回数についての記述を以下のように変更いたしました。

「線形探索法では、N個のデータの中から目的のデータを探すときの平均比較回数は「(N＋1)／2回」です。ただし、目的のデータが探索対象内に存在すると判っているときには、最後の要素を比較する必要がなくなるので平均比較回数は「N／2回」になります。この問題では「目的のデータは必ず表の中に存在するものとする」という条件があるので、平均比較回数には「N／2回」を用います。」

平成30年春期問6
  https://www.ap-siken.com/kakomon/30_haru/q6.html

管理人様
ありがとうございます。ただ、少し漏れがあります。

2回目の、ブロック内の線形探索の平均比較回数がm／2回というのは、「N／2回」を用いるのはいいのですが、1回目の、各ブロックの最後尾データの線形探索は、考え方が違います。

目的のデータと一致するかどうかという探し方ではなく、
目的のデータ≦各ブロックの最後尾データ
を順次チェックし、成り立てばそのブロックにあることになるし、最後より一つ前のブロックまで成り立たなければ、最後のブロックにあることになり、最小は1回、最大はn／m－1回で、平均n／2m回です。このときに重要な条件が、全てのデータが昇順だから、各ブロックの最後尾データも昇順となっていることです。

> 管理人様
私も[1145]のスレッドには参加していました。
確かに、助け人さんの説明の方が合っているかもと思ったりもしますが、
現状では少数の意見です。
公式どおりでもmが十分に大きいので近似値とできるはずです。
「別解」などにするのが妥当ではないでしょうか？

1回目の探索の平均比較回数が「n／2回」になる理由は理解しております。

まだアップロードはしておりませんが、最後尾のデータの並びが昇順になっている説明を加えた以下の文章を考えております。いかがでしょうか？

「最初は、n個のデータをm個ごとのブロックに分割した最後尾のデータのみを探索します。表のデータは昇順に整列されているので、各ブロック最後尾の並びも昇順になっており線形探索を適用できます。探索するデータ数は n／m個 なので、目的のデータが存在するブロックを探し出す（または最後のブロックに存在することが確定する）までの平均比較回数は、…」

管理人様
何度もすみません。

まず、「各ブロック最後尾の並びも昇順になっており線形探索を適用できます。」ということですが、線形探索は、昇順または降順になっている必要がありません。その必要があるのは、2分探索の方です。

目的のデータとn／m個の各ブロック最後尾を比較する向きは、確かに線形(左から右へ)ではありますが、線形探索ではありません。線形探索は、目的のデータと一致するものがあるかを調べるために、左から右へ向かって比較し、一致すればあったとなるし、一致しなかったらなかったとなります。

ここでは、一致するものはあるかではなく、
目的のデータ≦各ブロックの最後尾データ
を左から右へ向かって判断し、成り立てばそのブロックにあることになるし、最後の一つ前まで成り立たなければ最後のブロックにあることになる、という、線形探索の変形です。

整理すると、1回目は昇順になっている必要のある変形線形探索、2回目は昇順になっている必要はないが、たまたま昇順になっている線形探索です。

> 管理人様
> 助け人さん
「線形探索法では、N個のデータの中から目的のデータを探すときの平均比較回数は「(N＋1)／2回」です。ただし、目的のデータが探索対象内に存在すると判っているときには、最後の要素を比較する必要がなくなるので平均比較回数は「N／2回」になります。」

目的のデータが探索対象内に存在するからこそ、平均比較回数は「(N＋1)／2回」というのが公式のはずです。私の参考書もそうですが、インターネット上でもそういった情報しか見つけられませんでした。
（ちなみに、目的のデータが存在しないケースを含む場合は、一例では存在する確率・存在しない確率を用いるらしいです）
そして、「(N＋1)／2」というのが公式ということは「最後の要素まで比較する」ことを意味し、「最大はN」を意味しています。
つまり、新しい解説は今までの公式を変えてしまうことになります。

最後の要素を比較する必要がないから最大は「N－1」や、平均比較回数は「N／2回」などのように、今までの公式を変えるような主張ならば信頼できるソースを提示すべきではないでしょうか？

管理人様
今さら聞けないさん

今さら聞けないさんのおっしゃるように、目的のデータが探索対象内に存在する場合、平均比較回数は「(N＋1)／2回」ということで、収束させましょう。

H26春期 問6
https://www.ap-siken.com/kakomon/26_haru/q6.html
の正解エでは、(n＋1)／2に、存在する確率を掛けていますし。

最後のデータの一つ前まで一致しなければ、最後のデータは比較しなくていい、というのは、ヘソ曲がりかもしれません。私がこれを主張したのは、このH30春期 問6と同題のH24春期 問9のアイテックの解説で、目的のデータが存在する場合は最大N－1回としており、一瞬アレと思ったのですが、そうでこそ正解のとおりになり、納得したからです。

ただ、1回目の各ブロックの最後尾データの探索は、目的のデータと一致するかどうかという探し方ではなく、
目的のデータ≦各ブロックの最後尾データ
を順次チェックし、成立するまで最後のブロックまで探すという説明はしていただきたい。

そうすると、以下のようになります。
1回目：(n／m＋1)／2
2回目：(m＋1)／2
合計：n／2m＋m／2＋1
ここで、mは十分大きいので、n／2m＋m／2

でも、私は、m／2に比べて十分小さい1を落とすのはわかりますが、n／2mを残すのだけは納得がいきませんが、これしか選べません。mは十分大きいだけでなく、nはmに比べて十分大きいmの倍数というのならわかります。

あれから寝付く前、起きる直前に頭をよぎった内容です。これで終わりです。

nが1,000,000のとき、
mを100,000とすると、(10＋１)／2＋(100,000＋1)／2＝5.5＋50,000.5＝50,006
mを10,000とすると、(100＋１)／2＋(10,000＋1)／2＝50.5＋5,000.5＝5,051
mを1,000とすると、(1,000＋１)／2＋(1,000＋1)／2＝500.5＋500.5＝1,001
mがnの平方根のときに最適化される。

でも、もし、n個をm個ごとのブロックに分けるだけでなく、m個をp個ごとのブロックに分け、p個をq個ごとのブロックに分け、・・・、と考えると、
nが1,000,000のとき、
mを100,000として5.5回、pを10,000として5.5回、qを1,000として5.5回、rを100として5.5回、sを10として5.5回、最後に10個に対して5.5回、計5.5×6＝33回で済む。これはまさに10分探索ではないかと！

これを2分探索風にアレンジする。
nが16のとき、
mを8として1.5回、pを4として1.5回、qを2として1.5回、最後に2個に対して1.5回、計1.5×4＝6回。でも、これは2分探索の平均比較回数である、log(2)16＝4回に合わないなと。なぜなら、後半のブロックも比較しているからであり、2分探索では、中央にあるデータと比較するだけで、前半にあるか後半にあるかを判断するから。

というように、もしかして、昇順のデータに対して線形探索を行う効率的な方法を考えることから2分探索に行き着いた、という経緯かもしれないなと思いました。

助け人さん、大変ご苦労様です。

> 目的のデータが探索対象内に存在する場合、平均比較回数は「(N＋1)／2回」ということで、
> 収束させましょう。
> H26春期 問6の正解エでは、(n＋1)／2に、存在する確率を掛けていますし。
H26春期 問6の問題は気づきませんでした。参考になりました。
やはり現状は公式どおりの方が良さそうですね。

> でも、私は、m／2に比べて十分小さい1を落とすのはわかりますが、n／2mを残すのだけは
> 納得がいきませんが、これしか選べません。mは十分大きいだけでなく、
> nはmに比べて十分大きいmの倍数というのならわかります。
同感ですね。私も引っかかっています。

> 最後のデータの一つ前まで一致しなければ、最後のデータは比較しなくていい、というのは、
> ヘソ曲がりかもしれません。
滅相もございません。あり得る考えだと思います。
あちこちで同じような意見が出てくれば変わってくるかもしれませんね。

助け人さん、今さら聞けないさん

貴重なご意見をいただき誠にありがとうございます。本問の解説につきましては、平均比較回数を(N＋1)／2回とし、以前に記載していたように m が十分に大きいので近似できるという方向でまとめようと考えております。また平均比較回数をn／2回として考えるという解釈につきましては、解説の最後に補足説明として追記いたしました。

>ただ、1回目の各ブロックの最後尾データの探索は、目的のデータと一致するかどうかという探し方ではなく、目的のデータ≦各ブロックの最後尾データを順次チェックし、成立するまで最後のブロックまで探すという説明はしていただきたい。

こちらのご要望については、1回目の比較の説明中に以下の文章を加えました。

「最初は、n個のデータをm個ごとのブロックに分割した最後尾のデータのみを探索します。表のデータは昇順に整列されているので、各ブロック最後尾の並びも昇順になっているはずです。この最後尾データの並びに対して「目的のデータ≦各ブロックの最後尾データ」を順次チェックし、目的のデータが存在するブロックを探します。
この1回目の探索では、データを1つずつチェックしていくので線形探索の考え方を準用できます。」

平成30年春問6
  https://www.ap-siken.com/kakomon/30_haru/q6.html

同題につきましては未だ修正しておりませんが、この解説の目途がつき次第、修正作業を実施させていただく予定です。

管理人様
解説を拝見しました。ありがとうざいました。

今さら聞けないさん
スレッド[1145]のT.S.さん、ぽちさん
皆さんのそれぞれの問題提起で大変な展開になりましたが、一つの問題でこれだけ議論することができました。まさに切磋琢磨です。

管理人様、助け人さん
こちらこそ意見を受け止めてくださり、ありがとうございました。
大変お疲れ様でした。