データ構造とアルゴリズム ( 第 7 回 )

(1)

データ構造とアルゴリズム ( 第 7 回 )

静岡大学工学部安藤和敏

2006.12.21

http://coconut.sys.eng.shizuoka.ac.jp/algo/06/

(2)

第 4 章データの探索

4.1

探索の定義と簡単な探索アルゴリズム

4.2 2

分探索法

4.3

ハッシュ法

(3)

第 4 章データの探索

4.1

探索の定義と簡単な探索アルゴリズム

4.2 2

分探索法

4.3

ハッシュ法

(4)

定義 4.1 （探索）

探索とは，入力として n 個のデータ d⁰, d¹, ...

, d^n-1 と値 x が与えられたときに，データ中から x = dⁱ となる dⁱ をみつける操作である

．

探索する値がデータの中に存在しないときは，

“ データ中に存在しない”という出力を行う．

(5)

日常生活における探索の例

n 個のデータ d⁰, d¹, ... , d^n-1 ：辞書に載っているすべての単語

探索する値 x ：調べたい単語

n 個のデータ d⁰, d¹, ... , d^n-1 ：オークションに出品されているすべての商品名

探索する値 x ：欲しい物の商品名辞書

インターネット・オークション

(6)

簡単な探索アルゴリズム

以降では，与えられる n 個のデータ d⁰, d¹, ... , d^n-1 ，および，探索する値 x は，すべて正の整数であると仮定する．

(7)

アルゴリズム 4.1 （線形探索）

入力： n 個のデータを格納する配列 D と探索する値 x

i = 0;

while (i < n) { if (x == D[i]) {

D[i] を出力してアルゴリズムを終了 ;

} else { i = i + 1;

}

“x は存在しない”と出力 ;

}

(8)

アルゴリズム 4.1 の実行例

17 39 1

D 5

[0] [1] [2] [3] [4]

9 24 2 11

[5] [6] [7]

23 6 13 [8] [9] [10]

29 28 20 [11] [12][13]

33 [14][15]

15

23

(9)

アルゴリズム 4.1 の時間計算量

17 39 1

D 5

[0] [1] [2] [3] [4]

9 24 2 11

[5] [6] [7]

23 6 13 [8] [9] [10]

29 28 20 [11] [12][13]

33 [14][15]

15

最良時間計算量は O(1) 最悪時間計算量は O(n) 平均時間計算量は O(n)

(10)

第 4 章データの探索

4.1

探索の定義と簡単な探索アルゴリズム

4.2 2

分探索法

4.3

ハッシュ法

(11)

2 分探索法

D[0] < D[1] < D[2] < ... < D[n-1].

入力データが昇順に（小さい順）に，配列 D に格納されていると仮定する :

(12)

2 分探索法（１）

探索する値 x と配列の中央にあるデータと比較する．

D

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11] [12][13][14][15]

x と比較す

る

(13)

2 分探索法（２）

中央のデータと x が等しい場合，そのデータを出力して探索を終了する．

D

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11] [12][13][14][15]

D[7] == x の場合

(14)

2 分探索法（２）

中央のデータが x より小さい場合， x は中央のデータより左側にはないので，探索範囲を

入力 : n 個の昇順データを格納する配列 D と探索する値 x

left = 0; right = n -1; mid = (left + right)/2;

while (left < right) {

if (D[mid] == x) { D[mid] を出力しアルゴリズムを終了 ; } else if (D[mid] < x) { left = mid + 1; }

else { right = mid -1; } mid = (left + right) /2;

}

(21)

アルゴリズム 1.3 の動き

1 回目

1 2 5

D 6 9 11 13 15 17 20 23 24 28 29 33 39

1 2 5

D 6 9 11 13 15 17 20 23 24 28 29 33 39

1 2 5

D 6 9 11 13 15 17 20 23 24 28 29 33 39

1 2 5

D 6 9 11 13 15 17 20 23 24 28 29 33 39

2 回目

3 回目

4 回目

(22)

２分探索法の時間計算量

調べる配列の大きさは， while の繰り返しごとに

，半分以下になる．したがって， k 回目の while の繰り返しを実行したときに，配列の大きさは

以下になる．

n

k

 



 



 2 1

(23)

２分探索法の時間計算量（続き）

したがって，アルゴリズムが終了するまでの

while 文の繰返し回数 k は

を満たす．

2 1

1   



 



 n

k

n  2

k

上式を書き換えると，　　　　　であるから，

を得る．

したがって，最悪時間計算量は O(log n) である．

k

n 

log

(24)

宿題

第 4 章の演習問題のできるところすべて．（提出しなくてもよい．巻末の解答例を見て自己採点せよ．）

(25)

お知らせ

2007 年 1 月 1 １日のこの時間帯に中間試験を行う

．詳細は Web ページ

http://coconut.sys.eng.shizuoka.ac.jp/algo/06/

に掲載予定です．

データ構造とアルゴリズム ( 第 7 回 )