相異なる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で質問しましょう!
似たような質問が見つかりました
- Excel(エクセル) VLOOKUP が機能しない、その原因は何 ? 8 2022/10/19 12:06
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- 統計学 確率統計の問題です。 3 2022/04/07 04:39
- Visual Basic(VBA) 顧客ごとに違う点検案内を作成するマクロ 4 2022/09/16 05:34
- PHP PHP ページング データベース 1 2022/06/16 10:30
- その他(クラウドサービス・オンラインストレージ) Microsoft Listと同じ使い方が出来るサービス 1 2022/11/21 09:01
- その他(データベース) pythonでsqlight勉強中、クエリー結果の利用法教えて下さい 1 2022/04/28 20:38
- C言語・C++・C# C言語初心者 ポインタについて、お助けください、、 2 2023/03/15 23:50
- 数学 特定の座標点を通る回帰を行う方法について。 2 2022/10/10 10:27
- Excel(エクセル) Excelでの検索結果を含む行だけを表示させたい 5 2023/03/10 17:08
このQ&Aを見た人はこんなQ&Aも見ています
-
新NISA制度は今までと何が変わる?非課税枠の拡大や投資対象の変更などを解説!
少額から投資を行う人のための非課税制度であるNISAが、2024年に改正される。おすすめの銘柄や投資額の目安について教えてもらった。
-
平成15年春の問5が解説を読んでもわからない
情報処理技術者・Microsoft認定資格
-
16進小数0.Cを10進数小数に変換したら0.75になりますがわたし自
LANケーブル・USBケーブル
-
10進数の分数 1/32 を16進数の小数で表すと?(基本情報試験)
情報処理技術者・Microsoft認定資格
-
-
4
関数f(x)が区間0≦x≦1で単調に増加する条件は0<x<1のとき、f
数学
関連するカテゴリからQ&Aを探す
医師・看護師・助産師
薬剤師・登録販売者・MR
医療事務・調剤薬局事務
歯科衛生士・歯科助手
臨床検査技師・臨床工学技士
理学療法士・作業療法士・言語聴覚士
臨床心理士・心理カウンセラー・ソーシャルワーカー
介護福祉士・ケアマネージャー・社会福祉士
弁護士・行政書士・司法書士・社会保険労務士
フィナンシャルプランナー(FP)
中小企業診断士
公認会計士・税理士
簿記検定・漢字検定・秘書検定
情報処理技術者・Microsoft認定資格
TOEFL・TOEIC・英語検定
建築士
インテリアコーディネーター
宅地建物取引主任者(宅建)
不動産鑑定士・土地家屋調査士
マンション管理士
電気工事士
美容師・理容師
調理師・管理栄養士・パティシエ
シェフ
保育士・幼稚園教諭
教師・教員
国家公務員・地方公務員
警察官・消防士
その他(職業・資格)
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
営業秘密とは、どこからのこと...
-
データベース関係で、データの...
-
「データをプロットする」の意...
-
大学の科研費について
-
編集用語「実データ」とは?
-
ネガデータって何?
-
農林水産省の食糧需給表につい...
-
海外とのやり取り(英語)に関す...
-
バスとチャネルってどう違うん...
-
販売王を2台のパソコンで操作...
-
身の回りの困り事を解決する課...
-
TKC会計 FX2について
-
ExcelのSUMIFS関数について色々...
-
勘定奉行をつかって前年対比が...
-
オープンアドレス法の欠点
-
製薬開発職における研究概要
-
TKCシステムへの読み込み
-
Macのデータバックアップしたい...
-
EEPROMのデータが壊れる。
-
スタックについて
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
データベース関係で、データの...
-
「データをプロットする」の意...
-
海外とのやり取り(英語)に関す...
-
編集用語「実データ」とは?
-
ネガデータって何?
-
EEPROMのデータが壊れる。
-
身の回りの困り事を解決する課...
-
ExcelのSUMIFS関数について色々...
-
TKC会計 FX2について
-
弥生会計のデータを
-
勘定奉行をつかって前年対比が...
-
Macmini 14.1.2 ログイン画面に...
-
給与奉行のデータをエクセルに...
-
CADデータの所有権について
-
販売王を2台のパソコンで操作...
-
Excel のサンプルデータ、事例...
-
情報処理の問題で、これがよく...
-
「N月N日のデータ」の訳
-
RAWデータを請求する根拠
-
access 登録したデータを修正...
おすすめ情報