相異なる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も見ています
-
【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
ロボットの住む世界で流行ってる罰ゲームとは?
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
16進小数0.Cを10進数小数に変換したら0.75になりますがわたし自
LANケーブル・USBケーブル
-
平成15年春の問5が解説を読んでもわからない
情報処理技術者・Microsoft認定資格
-
関数f(x)が区間0≦x≦1で単調に増加する条件は0<x<1のとき、f
数学
-
関連するカテゴリからQ&Aを探す
医師・看護師・助産師
薬剤師・登録販売者・MR
医療事務・調剤薬局事務
歯科衛生士・歯科助手
臨床検査技師・臨床工学技士
理学療法士・作業療法士・言語聴覚士
臨床心理士・心理カウンセラー・ソーシャルワーカー
介護福祉士・ケアマネージャー・社会福祉士
弁護士・行政書士・司法書士・社会保険労務士
フィナンシャルプランナー(FP)
中小企業診断士
公認会計士・税理士
簿記検定・漢字検定・秘書検定
情報処理技術者・Microsoft認定資格
TOEFL・TOEIC・英語検定
建築士
インテリアコーディネーター
宅地建物取引主任者(宅建)
不動産鑑定士・土地家屋調査士
マンション管理士
電気工事士
美容師・理容師
調理師・管理栄養士・パティシエ
シェフ
保育士・幼稚園教諭
教師・教員
国家公務員・地方公務員
警察官・消防士
その他(職業・資格)
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
データベース関係で、データの...
-
「データをプロットする」の意...
-
編集用語「実データ」とは?
-
ネガデータって何?
-
figmaの元データは残したまま、...
-
EEPROMのデータが壊れる。
-
販売王を2台のパソコンで操作...
-
会計王9で2台のPCでデータを...
-
TKC会計 FX2について
-
UPSにつなげる機器にはどんなも...
-
仕事で商品画像を早く受け取る方法
-
【弥生会計】会計期間の変更方...
-
バスとチャネルってどう違うん...
-
健康保険証
-
CADデータの所有権について
-
心疾患と急性心筋梗塞の患者数
-
レセプト電算化でのデータ
-
弥生販売のデータ移行について
-
飲食POSシステムの電子ジャーナル
-
iPadでのExcelで、上書きされた...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
データベース関係で、データの...
-
「データをプロットする」の意...
-
編集用語「実データ」とは?
-
figmaの元データは残したまま、...
-
ネガデータって何?
-
EEPROMのデータが壊れる。
-
弥生会計のデータを
-
TKC会計 FX2について
-
給与奉行のデータをエクセルに...
-
勘定奉行をつかって前年対比が...
-
オープンアドレス法の欠点
-
ExcelのSUMIFS関数について色々...
-
バスとチャネルってどう違うん...
-
情報処理の問題で、これがよく...
-
Excel 2007 グラフのデータテ...
-
弥生会計|前年度(過年度)の...
-
【弥生会計】会計期間の変更方...
-
access 登録したデータを修正...
-
Excelでネットが繋がらなくても...
-
Macmini 14.1.2 ログイン画面に...
おすすめ情報