データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏 2007.12.13.

Presentation on theme: "データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏 2007.12.13."— Presentation transcript:

1 データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏

2 第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

3 第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

4 定義4.1 （探索） 探索とは，入力として n 個のデータ d0, d1, ... , dn-1 と値 x が与えられたときに，データ中から x = di となる di をみつける操作である． 探索する値がデータの中に存在しないときは， “データ中に存在しない”という出力を行う．

5 日常生活における探索の例 辞書 n 個のデータ d0, d1, ... , dn-1 ：辞書に載っているすべての単語
探索する値 x ：調べたい単語 インターネット・オークション n 個のデータ d0, d1, ... , dn-1 ：オークションに出品されているすべての商品名 探索する値 x ：欲しい物の商品名

6 簡単な探索アルゴリズム 以降では，与えられる n 個のデータ d0, d1, ... , dn-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の実行例 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
[13] [14] [15] D 17 39 1 9 5 24 2 11 23 6 13 29 28 20 15 33 23

9 アルゴリズム4.1の時間計算量 最良時間計算量は O(1) 最悪時間計算量は O(n) 平均時間計算量は O(n) [0] [1] [2]
[3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] D 17 39 1 9 5 24 2 11 23 6 13 29 28 20 15 33 最良時間計算量は O(1) 最悪時間計算量は O(n) 平均時間計算量は O(n)

10 第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

11 2分探索法 入力データが昇順に（小さい順）に，配列D に格納 されていると仮定する:
D[0] < D[1] < D[2] < ... < D[n-1].

12 2分探索法（１） 探索する値 x と配列の中央にあるデータと比較する． xと比較する D [0] [1] [2] [3] [4] [5]
[6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 探索する値 x と配列の中央にあるデータと比較する．

13 2分探索法（２） 中央のデータと x が等しい場合，そのデータを出力して 探索を終了する． D[7] == x の場合 D [0] [1]
[2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 中央のデータと x が等しい場合，そのデータを出力して 探索を終了する．

14 2分探索法（２） 中央のデータが x より小さい場合，x は中央のデータより左側にはないので，探索範囲をD[8]～D[15]に限定できる．
D[7] < x の場合 D [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 中央のデータが x より小さい場合，x は中央のデータより左側にはないので，探索範囲をD[8]～D[15]に限定できる．

15 2分探索法（３） 中央のデータが x より大きい場合，x は中央のデータより右側にはないので，探索範囲をD[0]～D[6]に限定できる．
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 中央のデータが x より大きい場合，x は中央のデータより右側にはないので，探索範囲をD[0]～D[6]に限定できる．

16 2分探索法の実行例(x=23) D[7] < 23 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33
39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

17 2分探索法の実行例(x=23) 23 < D[11] D 1 2 5 6 9 11 13 15 17 20 23 24 28 29
33 39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

18 2分探索法の実行例(x=23) D[9] < 23 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33
39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

19 2分探索法の実行例(x=23) D[9] == 23 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

20 2分探索法の実現（アルゴリズム4.2） 入力: 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; } if (D[mid] == x) { D[mid] を出力; } else { “x は存在しない”と出力; }

21 アルゴリズム1.3の動き 1回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 2回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 3回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 4回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39

22 ２分探索法の時間計算量 調べる配列の大きさは， whileの繰り返しごとに，半分以下になる．したがって，k 回目のwhileの繰り返しを実行したときに，配列の大きさは 以下になる．

23 ２分探索法の時間計算量（続き） したがって，アルゴリズムが終了するまでのwhile文の繰返し回数 k は を満たす．
上式を書き換えると，　　　　　 であるから， を得る． したがって，最悪時間計算量は O(log n) である．

24 第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

25 ハッシュ法のアイデア データを格納するおおまかな場所を，そのデータがもつ情報から決定する． 部屋番号----> 部屋番号の左端の数字
４０３だから４階だな データを格納するおおまかな場所を，そのデータがもつ情報から決定する． 部屋番号----> 部屋番号の左端の数字

26 ハッシュ関数 データ x から，そのデータを格納する大まかな場所を決定する関数をハッシュ関数呼んで，hash(x) と表す． 例）
x　----> hash(x) = (x の左端の数字）

27 データを格納するための配列 H データを格納する場所として，配列Hを準備する．
ハッシュ法で用いる配列のサイズは格納するデータのサイズ n の 1.5～2倍とするのが一般的である． ここでは，Hのサイズは，1.5nとしておく．

28 ハッシュ法によるデータの格納の例 データの集合
{17, 39, 1, 9, 5,24, 2, 11, 23, 6, 13, 29, 28, 20, 15, 33} を考える．（n=16) データを格納するための配列 H のサイズは 16×1.5 =24 hash(x) = (x を 24で割った余り）= x%24 H [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]

29

30 アルゴリズム4.3 （ハッシュ法によるデータの格納）
入力：サイズ m のH，および，n個のデータを格納する配列D for (i=0; i<n; i = i+1) { k = hash(D[i]); while (H[k]にデータが格納されている) { k = (k+1)を m で割った余り; 　 } H[k] = D[i]; }

31 アルゴリズム4.4 （ハッシュ法による探索） 入力：アルゴリズム4.3によりデータの格納された配列Hと探索する値 x
k = hash(x); while (H[k]にデータが格納されている) { if (H[k] == x) { H[k]を出力してアルゴリズムを終了; } k=((k+1)をmで割ったあまり; “xは存在しない”と出力;

32 宿題 第4章の演習問題の全て．（提出しなくてもよい．巻末の解答例を見て自己採点せよ．）

33 お知らせ http://coconut.sys.eng.shizuoka.ac.jp/algo/07/
2007年12月20日(木）のこの時間帯に中間試験を行う． 詳細はWebページ に掲載予定です．