ヤマザキの地球偵察記録

ヤマザキさんの個人的な記録・備忘録です。

情報工学レクチャーシリーズ:アルゴリズムとデータ構造 第三章「データの探索」

探索

  • 多くのデータの中から目的のデータを見つけること

線形探索法(Linear search)

  • 配列の先頭から順番に探索を行う
  • 平均時間計算量は {O(n)}

二分木探索法

  • 配列の中身がソートされていることが前提条件
  • 配列の真ん中の値(mid)が目的の値(x)と一致しているか調べる。一致しているのなら出力して処理終了。
  • mid < x なら探索する範囲を配列の後半部分に、mid > x なら探索する範囲を配列の前半部分にし、再度処理1を行う
  • 処理1, 2を繰り返し行った結果、探索する範囲の配列長が1以下になったら配列の中にxは存在していないので、処理終了
  • 平均時間計算量は {O(log n)}

ハッシュ法

データの格納方法

  • ハッシュ関数を用いて目的のデータの格納場所を決定する
  • ハッシュ化した値が重複した場合は、ハッシュ化した値に1を加えた場所に格納するなどの処理を行う

データの探索

  • データの格納方法同様、ハッシュ関数を用いて目的のデータの探索場所を決定する
  • 探索場所に目的の値がない場合はハッシュ化した値に1を加えるなどの処理を行い、再度探索を行う
  • 最良時間計算量は{O(1)}、最悪時間計算量は{O(n)}
  • データの個数が {n} 個、配列長が {m} のとき、平均時間計算量は {O(\frac{m}{m-n})}、基本的には {O(1)} になる