データ構造と アルゴリズム 第八回 知能情報学部 新田直也 探索 探索: 表からデータを探し出す. 名前 点数 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; }; struct Record int n = 0; { // 重複しない // 0以上と仮定 table[100]; // レコード数(<= 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 key key 1 1 1 3 3 3 4 4 4 8 8 8 13 13 14 14 middle → 14 18 18 18 20 middle → 20 21 21 21 25 25 25 middle → 13 < 14 (key) > 14 (key) 20 二分探索(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) { O(log n) int pos; pos = データを挿入すべき位置; 配列中のpos以降の要素を1つづつ後ろにずらす; O(n) table[pos].key = key; table[pos].data = data; O(1) } 線形探索法と二分探索法の比較 登録 探索 線形探索法 O(1) O(n) 二分探索法 O(n) O(log n) 二分探索の高速化 登録が遅い原因 データをずらすのに時間がかかっている. 線形リストを使えないか? struct Record { int key; int data; struct Record *next; }; 簡単には高速化できない 線形リストではmiddleの位置を探すのに時間がかかる. (双方向リストでも同様) low middle … high …
© Copyright 2025 ExpyDoc