---
# System prepended metadata

title: Chapter16-8 「データを探索するアルゴリズム」
tags: [基本情報技術]

---

# Chapter16-8 「データを探索するアルゴリズム」

## 8/10(火)

###### tags:`基本情報技術`

さつき：
* 線形探索法
    * 先頭から順番に一致するかみていく
    * 効率面で非常にイケてない。
* 2分探索法
    * あらかじめデータ群が昇順または降順に並んでいる、というふうに規則性を持つ場合。
    * データのかたまりを分ける。
    * データの真ん中と比較し、どのかたまりに求めるデータがあるか絞り込んでいく。
* ハッシュ法
    * ハッシュ関数...一定の計算式のこと
    * データを格納するときに、計算式で求めた位置へと格納しておくので、参照するようにしてください。
* 各アルゴリズムにおける探索回数
    * 線形探索法...最小と最大の平均値
    * 2分探索法...log2n
    * ハッシュ法...１回
* 過去問
    * 問1...OK
        * 2分探索法は、必ずしも線形探索法より早く処理できるわけではない。データ列の先頭に検索する対象データがある場合、線形探索の方が早く探索できる。
    * 問2...OK
        * 格納場所の衝突が生じる可能性がある。



にわ：
- 読み込み
    * データを探索するアルゴリズム
        * 線形探索法
            * 先頭から順に探索
        * 2分探索法
            * データ群が昇順である、など規則性を持っている場合は使える。真ん中より大きい・小さいなど、探索対象を2つに分類して、2分の1ずつ削り落としながら探索していく。
        * ハッシュ法
            * データ格納時に「ハッシュ関数」という一定の計算式を使って特定の位置に格納し、同じハッシュ関数を使ってデータの位置を算出する。
    * 各アルゴリズムにおける探索回数
        * 線形探索法：（目的のデータが最初にある場合 + 最後にある場合）の平均 なので、(1+n)/2 回。
        * 2分探索法：データ件数をnとして、log2n
        * ハッシュ法：1回
- 過去問
    * 問１：OK
        * 「常に」って見落としがちなやつ。
    * 問２：OK



ちさと：
* データを探索
    * 線形探索法：先頭から順に見ていく
    * ２分探索法：データが昇順、降順に並んでいるなど規則性があるときに使える。
    * ハッシュ法：ハッシュ関数（一定の計算式）を使ってデータの格納位置を出す
* 探索回数
    * 線形探索法
        * 目的のデータが先頭にある場合：最小となる１回
        * 末尾にある場合：最大となるn回
        * 平均は（１＋n）÷２
    * ２分探索法
        * n個のデータの２分探索：log2n
        * logは何乗すればいいかを表す数
    * ハッシュ法
        * １回
* 過去問
    * 問１：おk
    * 問２：おk


まい：

* データを探索するアルゴリズム
  * 探索: 目的のデータを探し当てる処理
  * 線形探索法: 先頭から順に探索
    * 平均探索回数 (1 + n) / 2 
  * 2分探索法: ソートされてる場合は効率よく処理できる
    * 平均探索回数 log2n
      * nは2の何乗か？の意味
      * log2n + 1 = 最大探索回数
  * ハッシュ法: ハッシュ関数(一定の計算式)を用いてデータ格納位置を算出
    * シノニム: 計算の結果が重複、異なるレコードが同じアドレスで衝突 
    * 平均探索回数(シノニムを無視していい場合) 1

* 練習問題
  * 問1 ok
  * 問2 ok 