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

Presentation on theme: "データ構造と アルゴリズム 第八回 知能情報学部 新田直也."— Presentation transcript:

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

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

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

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

5 線形探索(登録) 表のデータ構造： 配列 登録のアルゴリズム： 最後に追加するだけ． 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++; }

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

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

8 二分探索(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)

9 二分探索(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;

10 二分探索(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);

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

12 二分探索(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)

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

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

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