データ構造と アルゴリズム 第八回 知能情報学部 新田直也

探索 探索： 表からデータを探し出す． 名前 点数 Eric 90 Tomas 50 Frederic 80 Mary 95 John 35

「表」抽象データ型(1) 表： 順序を持たない． キーとデータの対応関係． キーは重複しない． リストとの違いに注意． 順不同 キー データ 名前 点数 Eric 90 Tomas 50 Frederic 80 Mary 95 John 35 順不同 レコード

「表」抽象データ型(2) 表に必要な操作： 登録 インタフェース 削除 探索 名前 点数 Eric 90 Tomas 50 Frederic 80 Mary 95 John 35 インタフェース 削除 探索

線形探索(登録) 表のデータ構造： 配列 登録のアルゴリズム： 最後に追加するだけ． struct Record { int key; // 重複しない int data; // 0以上と仮定 }; struct Record table[100]; int n = 0; // レコード数(<= 100) void add(int key, int data) { if (n < 100) { table[n].key = key; table[n].data = data; n++; }

線形探索(探索) 探索アルゴリズム： 先頭から順番に… int search(int key) { int i; for (i = 0; i < n; i++) { if (table[i].key == key) return table[i].data; } return -1;

線形探索の最悪時間計算量 レコード数 n を入力のサイズとする． 探索アルゴリズムをもっと早くできないか… 登録アルゴリズム： O(1) 探索アルゴリズム： O(n) 探索アルゴリズムをもっと早くできないか…

二分探索(1) 表のデータ構造： 配列(キーでソート済み) 探索のアルゴリズム： 候補を半分づつ絞っていく… key 1 3 4 8 13 14 18 20 21 25 key 1 3 4 8 13 14 18 20 21 25 key 1 3 4 8 13 14 18 20 21 25 middle → < 14 (key) middle → middle → > 14 (key)

二分探索(2) 二分探索のプログラム： int binary_search(int key) { int low, high, middle; low = 0; high = n – 1; while (low <= high) { middle = (low + high) / 2; if (key == table[middle].key) return table[middle].data; else if (key < table[middle].key) high = middle - 1; else low = middle + 1; } return -1;

二分探索(3) 二分探索のプログラム(再帰型)： int binary_search(int key) { return binary_search_sub(0, n-1, key); } int binary_search_sub(int low, int high , int key) { if (low > high) return -1; middle = (low + high) / 2; if (key == table[middle].key) return table[middle].data; else (key < table[middle].key) return binary_search_sub(low, middle – 1, key); else return binary_search_sub(middle + 1, high, key);

二分探索(4) 二分探索の時間計算量 1回のループでデータ量が半分になる． →最悪でも，log2n 回のループ 1回のループはたかだか4ステップ O(1) × O(log n) = O(log n) →線形探索より速い!!

二分探索(5) 登録のアルゴリズム： データは常にソートされている必要がある． →挿入位置を探す必要． →挿入位置の後ろのデータをずらす必要． 挿入位置は二分探索で可能． int add_binary(int key, int data) { int pos; pos = データを挿入すべき位置; 配列中のpos以降の要素を1つづつ後ろにずらす; table[pos].key = key; table[pos].data = data; } O(log n) O(n) O(1)

線形探索法と二分探索法の比較 登録 探索 線形探索法 O(1) O(n) 二分探索法 O(log n)

二分探索の高速化 登録が遅い原因 データをずらすのに時間がかかっている． 線形リストを使えないか？ struct Record { int key; int data; struct Record *next; };

簡単には高速化できない 線形リストではmiddleの位置を探すのに時間がかかる． （双方向リストでも同様） low middle high … …