相異なるn個のデータが昇順に整列された表がある。この表を1ブロックm個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、目的のデータの存在するブロックを探し出す。次に当該ブロック内を線形探索して目的のデータを探し出す。このときの平均探索回数はどれか。ここで、 m<nとし、目的のデータは必ず表の中に存在するものとする。
答えは m/2 + n/2m なのですが、
目的のデータが存在したブロックの中での
線形検索の結果でm/2 となるのは分かるのですが、
なぜ、n/2mで目的のブロックを見つけることが
できるのかが分かりません。
例えば、
(1,8,9),(10,13,14),(17,19,20) で
3つずつのブロックに分けて各ブロックの最後尾
の数だけで線形検索を行うってことは、
9,14,20 で 検索するってことで 平均2/3
で見つかることは分かります。
けれど、目的の数値が9,14,20 以外の数字
だったら、目的の数値が
含まれるブロックが見つからない気がするのですが。
例えば目的の数値が、8だったら、
最後尾の数だけで、線形検索しても
該当の数がないので、分からないと思うのです。
どなたか、お馬鹿な私に分かりやすく教えてください。
よろしくお願いします。
No.3ベストアンサー
- 回答日時:
この探索法は,たぶん,索引順編成ファイルにおける探索法(の原理)のことを言っているのだと思います。
それはともかく,この例では,全部でn個のデータを1ブロックm個のデータに分割しますので,ブロック数は(n/m)個です。
で,このような問題で「(平均)探索回数」というのは,「(平均)比較回数」と考えたほうが分かりやすいのではないかと思います。
探索しているデータの含まれるブロックを見つけ出すまでの,ブロック探索の回数は最大で(n/m)回(最小は0回?)なので,平均すると(1/2)×(n/m)回となります。
>目的のデータが存在したブロックの中での
線形検索の結果でm/2 となるのは分かるのですが、
というわけですから,合計の平均探索回数は,
>答えは m/2 + n/2m なのですが、
となります。
これが1個のデータを探索するときの平均線形探索回数(=目的のデータが含まれるブロックを見つけ出し,さらにブロック内で目的データを見つけ出す までの合計探索回数 の平均値)です。
次の疑問点についてですが,
>例えば目的の数値が、8だったら、
最後尾の数だけで、線形検索しても
該当の数がないので、分からないと思うのです。
線形検索をするときに,たとえばSEAMOONさんのデータ例で,「17」を探しているとすれば,
「17以上」と言う条件で探索します。
そうすると,ブロック探索では,「9」と「14」は適さず「20」が条件に適うものとして第3ブロックが探索結果となります。(実探索(比較)回数=3)
>9,14,20 で 検索するってことで 平均2/3
で見つかることは分かります。
違います。平均は(1/2)×(9/3)=3/2回 となります。(個人的意見としては,(1+3)/2=2が平均回数だと思うのですが)
次に第3ブロック内で同様に「17以上」(今度は「17と等しい」でもいいですが)という条件でブロック内線形探索をすると1回の探索(実回数1回の比較)で目的のデータにたどり着くことになります。
No.2
- 回答日時:
いくつか解説ページがありましたのでURLを貼っておきます。
http://www.jtw.zaq.ne.jp/kayakaya/new/kihon/h12a …
http://mt-net.vis.ne.jp/ADFE_mail/0140.htm
ありがとうございます。
読んでみてもいまいち、理解できません。
なぜ、m/2+n/2mなのでしょう。
m/2 × n/2m なら意味が分かる気が
するのですが。
ん、平均回数を求めるからなのかなぁ。
全回数を求める時はどうなるんだろう
No.1
- 回答日時:
まず、1つ誤解。
>最後尾の数だけで、線形検索しても
>該当の数がないので、分からないと思うのです。
昇順に整列されているので、検索対象の数値が最後尾の数値以下なら、そこのブロックに含まれることが分かります。
m/2 + n/2m の n/2m は、n/m ÷ 1/2 かな、と。
つまり、データ数÷ブロック数の半分。
この回答への補足
>検索対象の数値が最後尾の数値以下なら、
この部分は計算式には表れてこないのでしょうか?
仮に昇順に並んでいないとしたら、
その場合計算式はどうなるのでしょう。
混乱中
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
医師・看護師・助産師
薬剤師・登録販売者・MR
医療事務・調剤薬局事務
歯科衛生士・歯科助手
臨床検査技師・臨床工学技士
理学療法士・作業療法士・言語聴覚士
臨床心理士・心理カウンセラー・ソーシャルワーカー
介護福祉士・ケアマネージャー・社会福祉士
弁護士・行政書士・司法書士・社会保険労務士
フィナンシャルプランナー(FP)
中小企業診断士
公認会計士・税理士
簿記検定・漢字検定・秘書検定
情報処理技術者・Microsoft認定資格
TOEFL・TOEIC・英語検定
建築士
インテリアコーディネーター
宅地建物取引主任者(宅建)
不動産鑑定士・土地家屋調査士
マンション管理士
電気工事士
美容師・理容師
調理師・管理栄養士・パティシエ
シェフ
保育士・幼稚園教諭
教師・教員
国家公務員・地方公務員
警察官・消防士
その他(職業・資格)
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
データベース関係で、データの...
-
「データをプロットする」の意...
-
編集用語「実データ」とは?
-
ネガデータって何?
-
figmaの元データは残したまま、...
-
情報処理の問題で、これがよく...
-
チラシやPOPの元データは無償で...
-
弥生会計|前年度(過年度)の...
-
給与奉行のデータをエクセルに...
-
Macmini 14.1.2 ログイン画面に...
-
弥生会計のデータを
-
EEPROMのデータが壊れる。
-
健康保険証
-
外付けハードディスクにSQL...
-
TKC会計 FX2について
-
ピボットテーブル
-
勘定奉行をつかって前年対比が...
-
Excelでネットが繋がらなくても...
-
that節がどこにかかるか悩んで...
-
ロジカルシンキングについて
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
データベース関係で、データの...
-
「データをプロットする」の意...
-
編集用語「実データ」とは?
-
ネガデータって何?
-
Excelでネットが繋がらなくても...
-
EEPROMのデータが壊れる。
-
弥生会計のデータを
-
TKC会計 FX2について
-
figmaの元データは残したまま、...
-
勘定奉行をつかって前年対比が...
-
給与奉行のデータをエクセルに...
-
情報処理の問題で、これがよく...
-
Excel 2007 グラフのデータテ...
-
Excel のサンプルデータ、事例...
-
初級シスアド
-
スタックについて
-
TKCシステムへの読み込み
-
CADデータの所有権について
-
access 登録したデータを修正...
-
販売王を2台のパソコンで操作...
おすすめ情報