データ構造と
アルゴリズム
第八回
知能情報学部
新田直也
探索
探索： 表からデータを探し出す．
名前
点数
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 2024 ExpyDoc
