( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる ( 復習 ) アルゴリズムの計算量 探索アルゴリズムとは オーダー記法 (O 記法 ) 問題のサイズ n に対して, 予測される計算量を定数部分を省略して表現する方法例 )n +n-0 O(n ) 00n+9logn+0000 O(n) 主要項 (n の増加に対して最も増加率が高い項 ) のみ取り出して, 定数部分を省略 多くの情報の中から特定の値を持つデータを探す手順 データは幾つかのレコードから構成され, 各レコードは探索のためのキーを持っているものとする 単語 発音 品詞 意味 apple [aepl] 名詞 リンゴ grape [greip] 名詞 ぶどう 主に三つの機能から構成キーの値は 探索 : 与えられたデータを探し出す互いに異なるとする 挿入 : データを表に登録する 削除 : 与えられたデータを削除する 4
線形探索 ( 逐次探索 順探索 ) データ管理 : 配列に格納 探索 : 配列の最初のレコードから順にキーを比較 procedure search(x: keytype; var found: boolean; var i: index); begin i:=; while (i n) and (x key[i]) do key[], key[n] に格納 i:=i+; found:= (i n); 探索キーがなければ i=n+に end; key[i] = x? 線形探索の計算量 最悪の場合 : n 回の比較 ( キーがなかった場合も含む ) 最良の場合 : 回の比較 平均 : (n+)/ 回の比較 計算量は O(n) 配列への挿入と削除 ( 並びを考えなくてよい場合 ) 挿入 : 最後に追加 削除 : 最後のレコードを削除位置に移動挿入 削除の計算量は O() 単語 apple grape lemon 探索テクニック : 番兵 検索キーのデータを末尾に入れておく 探索キーが見つかった時点で終了 見つかった場所が最後 ( 要素数 ) であった場合, キーがないと判定 ループ中に要素数を管理 ( 比較 ) する必要がなくなる key[i] = x? 4-000 x オーダーは変わらないが速度は上がる 7
二分探索 前提 : 入力データ ( 配列 :a[0], a[], a[n-]) は ( 昇順に ) 整列済みとする 方法 : 中央 (p=n/) の値 a[p] をキー k( 探索データ ) と比較 k<a[p] の場合 : k は p より左側にあるはず 次は左を探索 k>a[p] の場合 : k は p より右側にあるはず 次は右を探索 再帰的にこの操作を繰り返す a[0] 中央の値 n/ a[n-] 9 0 二分探索のアルゴリズム 二分探索のプログラム例 次のデータについて k = 70 を二分探索によって探索しなさい m 0 4 7 9 a[m] 0 40 70 0 9 時間計算量 : O(log n) 一回ごとに探索範囲が半分になる : log n 回の繰り返し binary_search(a, n, k) { i=0; j=n-; while(i <= j){ p = (i+j)/; w = a[p]; if(k < w) j = p - ; else if (k > w) i = p + ; else return p; } return -; } a: 配列, n: 個数, k: 探索する値 i: 左端の位置, j: 右端の位置 p: 中央の位置 k は左側 右端を p の一つ左に k は右側 左端を p の一つ右に k=w なら探索成功 p を返す 一致するものがなかった
二分探索のアルゴリズム 次のデータについて k = 70 を探索するときのプログラムの振る舞いを確かめなさい. 各ループごとに変数 i, j, p を書き出していく 終了時の i, j, p の値はどうなるか? m 0 4 7 9 a[m] 0 40 70 0 9 i=0 p=4 j=9 二分探索のアルゴリズム 次のデータについて k = 70 を探索するときのプログラムの振る舞いを確かめなさい. 各ループごとに変数 i, j, p を書き出していく 終了時の i, j, p の値はどうなるか? m 0 4 7 9 a[m] 0 40 70 0 9 i=0 p=4 j=9 i= p=7 j=9 一致するものが見つかったとき i p j になる i, p= j= i, p, j= 4 二分探索における挿入と削除 次のデータに k = を挿入する場合の計算量は? また,k = を削除する場合の計算量は? 配列 ()( 再掲 ) 配列 (array) 同じ型のデータを決まった個数だけ並べた構造 ほとんどのプログラミング言語に用意されている m 0 4 7 9 a[m] 0 40 70 0 9 番号 ( 添え字, インデックス ) を指定して, その位置にある要素を高速に参照できる 例. 配列 a 0 4 7-4 - - sum = a[] + a[4]; 定数オーダー O() で計算できる
配列 ()( 再掲 ) 要素数や並び方が固定 挿入 ( 削除 ) 時に要素をずらす必要がある 二分探索における挿入と削除 次のデータに k = を挿入する場合の計算量は? また,k = を削除する場合の計算量は? 挿入例 配列 a 9 コピー 0 4 7-4 - - m 0 4 7 9 a[m] 0 40 70 0 9 削除例 配列 a 0 4 7-4 - - 線形探索 : 挿入 / 削除が早いがO(), 探索が遅いO(n) 二分探索 : 挿入 / 削除が遅いがO(n), 探索が早いO(log n) 最悪 O(n) の計算時間 7 ハッシュ法 データの値から直接, 格納位置を計算する方法 キー値 xをh(x) を用いて, 配列の添え字やアドレスに変換する H(x) をハッシュ関数, ハッシュ関数が返す値をハッシュ値という 通常計算量はO() 例えばキーを格納する場所を キーの値を 0 で割った余り H(x)= x mod 0 とすると 0 90000 900 9000 4 904 900 7 90777 9 909 ハッシュ値 データ 9 ハッシュ法の問題とその解決法 衝突 異なったキーから同じハッシュ値が求まってしまう問題 同じ場所につのデータを格納できない 解決法 0 90000 900 オープンアドレス法 9000 衝突が発生した場合, 元のハッシュ値 + に格納する方法 4 904 904 7 90777 チェーン法 同じハッシュ値を持つデータをポインタを利用してつなぐ ( リスト構造 ) 9 909 ハッシュ値 データ 0
オープンアドレス法 衝突が発生した場合, 元のハッシュ値 + に格納する方法 挿入時 +の場所が空なら, そこに格納 既に格納されていたらその次へ 探索時 ハッシュ値の場所から一致するデータが見つかるまで+しながら探索 データが一致するか, 空のデータが現れると終了 0 90000 900 9000 4 904 904 904 7 90777 9 909 ハッシュ値 データ チェーン法 同じハッシュ値を持つデータをポインタでつなぐ ( リスト構造 ) 挿入時 ハッシュ値の場所が空でなければリストに新しいデータを挿入 探索時 ハッシュ値の場所を探索し, 不一致であればリストを探索 一致するか, リストの最後に到達すると終了 ハッシュ値 データ 0 90000 900 9000 4 904 904 7 90777 9 909 ハッシュ法の課題 計算量 キーをできるだけ一様に散らばせるようなハッシュ関数をいかに作るか 異なるキーが同じハッシュ値となった場合にどうするか ( 衝突の処理 ) 二分探索 : 探索は効率よいが, データの管理には手間がかかるハッシュ法 : 適応できる問題が限られる 挿入 探索 削除すべてを O(log n) の計算量でできないか? 4
二分探索木 二分探索木 (binary search tree) どの頂点も子の数が 以下 子は左か右のいずれかに位置する どの頂点でも, 以下が成り立つ左側の子孫の値 < その頂点の値 < 右側の子孫の値 例 : 例 : 4 二分木の定義 二分探索木における探索 根から葉へ次の手順を繰り返す 例 : 与えられた値とレコードを比較 小さければ左の子へ 大きければ右の子へ 右の二分探索木において を探索 根 4 0 子が一つでも左か右に 葉 0 二分木のデータ構造 一つの頂点のデータ構造 record left right C 言語での実装例 struct vertex { int record; /* 格納されているデータ */ struct vertex *left, *right /* 子の頂点へのポインタ */ } 二分探索木への挿入 木を下に降りるだけ降りてから頂点を挿入 できあがる木の形は挿入の順序で変わる (a) - - (b) - - (c) - - (d) - - (e) - - (f) - - 7
二分探索木への挿入 木を下に降りるだけ降りてから頂点を挿入 できあがる木の形は挿入の順序で変わる (a) - - (b) - - (c) - - 二分探索木による探索の計算量 木の形によって大きく変わる ( 例 : 7 要素の場合 ) (d) - - (e) - - (f) - - 9 完全二分木計算量 : O(log n) 計算量の平均は O(log n) 挿入の計算量は探索と同じ 最悪の場合計算量 : O(n) 0 二分探索木からの削除 二分探索木からの削除 葉の場合 ( 例 : を削除 ) 削除のみ 計算量 : 探索と同じ 葉の場合 ( 例 : を削除 ) 削除のみ 計算量 : 探索と同じ 一つしか子をもたない頂点の場合 ( 例 : を削除 ) 孫を子に持ってくる 4 4 0 0
二分探索木からの削除 二分探索木からの削除 葉の場合 ( 例 : を削除 ) 削除のみ 計算量 : 探索と同じ 葉の場合 ( 例 : を削除 ) 削除のみ 計算量 : 探索と同じ 一つしか子をもたない頂点の場合 ( 例 : を削除 ) 孫を子に持ってくる 一つしか子をもたない頂点の場合 ( 例 : を削除 ) 孫を子に持ってくる 両方の子を持つ場合 4 両方の子を持つ場合 ( 例 : 4 を削除 ) 左側の部分木の最大要素を持ってくる 0 ( 例 : 4 を削除 ) 左側の部分木の最大要素を持ってくる 0 4 まとめ 探索アルゴリズム () 線形探索 : 探索 O(n), 挿入 削除 O() 分探索 : 探索 O(log n), 挿入 削除 O(n) ハッシュ法 : 探索 O(), 挿入削除 O() どんなデータにも効果的なわけではない 分探索木 探索, 挿入, 削除をすべて O(log n) で実現