探索
- 多くのデータの中から目的のデータを見つけること
線形探索法(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)
になる