けけずんセルフハッキング

エンジニアっぽい雰囲気を醸しだしているかのようなブログです!

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

探索

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

線形探索法(Linear search)

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

二分木探索法

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

ハッシュ法

データの格納方法

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

データの探索

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