探索
アルゴリズム: 処理の手順
データを探すアルゴリズム: 線形探索、二分探索、ハッシュ法
時間計算量(オーダ)
データ数の増加に対する、処理時間の増加指標
オーダ記法(O記法)
O(n)などと記述して、効率の良さを表します。
(n)は処理するデータの数を表します。
O(1)
データ数にかかわらず、処理時間が一定
O(log n)
データ数が２倍に増えても、手間が一回増えるだけ
O(n)
データ数が10倍だと処理時間も10倍になります。
O(nlog n)
データ数が10倍だと処理時間も30倍になります。
O(nc) (cは小文字)
データ数が10倍だと
処理時間は二乗で100倍になります。
探索アルゴリズム
左のオーダ記法は時間計算量を表します。
線形探索 O(n)
順番に一つずつ、値の比較をしていく
二分探索 O(logn)
データの整列が前提条件
データを前半と後半に分けて行います。
小さい順に並んていれば
中央値>目的値 であれば前半を
中央値<目的値 であれば後半を探します。
ハッシュ法 O(1)
事前にハッシュ表に登録しておく必要がある。
ハッシュ関数を用いて
格納場所のアドレスを計算して、目的の値を探します。
線形探索
先頭要素から順に探します。
二分探索
データを昇順に整列させておく必要があります。
最小値と最大値の平均から中央値を算出する。
そこから前半と後半を分けて探索
仮に後半にあれば同様に分けて再探索
要は、中央値を求めて半分削って行って探索する方法です。
ハッシュ法
データの格納場所を計算によって決める方法です。
ハッシュ関数
データの格納場所を求める計算式
ハッシュ法により衝突(コリジョン)
異なったキーに大して、同じハッシュが計算されること
シノニム
後から、同じハッシュとして計算されたハッシュのこと
下記の方法で処理がされます。
- オープンアドレス法: 空き領域に格納
- チェーン法: 同じハッシュの値をリストで管理する方法