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

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

静岡大学工学部 安藤和敏

2007.12.13

第 4 章データの探索

4.1

4.2 2

4.3

第 4 章データの探索

4.1

4.2 2

4.3

定義 4.1 （探索）

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

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

．

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

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

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

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

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

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

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

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

簡単な探索アルゴリズム

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

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

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

i = 0;

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

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

} else { i = i + 1;

}

アルゴリズム

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

アルゴリズム 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)

第 4 章データの探索

4.1

4.2 2

4.3

2

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

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

2

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

D

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

x と比較す

る

2

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

D

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

D[7] == x の場合

2

中央のデータが x より小さい場合， x は中央

D

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

D[7] < x の場合

2

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

D

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

x < D[7] の場合

2 分探索法の実行例 (x=23)

1 2 5

D 9

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

6 11 13 15

[5] [6] [7]

17 20 23 [8] [9] [10]

24 28 29 [11] [12][13]

39 [14][15]

33 D[7] < 23

2 分探索法の実行例 (x=23)

1 2 5

D 9

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

6 11 13 15

[5] [6] [7]

17 20 23 [8] [9] [10]

24 28 29 [11] [12][13]

39 [14][15]

33 23 < D[11]

2 分探索法の実行例 (x=23)

1 2 5

D 9

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

6 11 13 15

[5] [6] [7]

17 20 23 [8] [9] [10]

24 28 29 [11] [12][13]

39 [14][15]

33 D[9] < 23

2 分探索法の実行例 (x=23)

1 2 5

D 9

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

6 11 13 15

[5] [6] [7]

17 20 23 [8] [9] [10]

24 28 29 [11] [12][13]

39 [14][15]

33 D[9] == 23

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;

アルゴリズム

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

2 回目

3 回目

4 回目

２分探索法の時間計算量

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

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

以下になる．

n

k

 



 



 2 1

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

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

while 文の繰返し回数 k は

を満たす．

2 1

1   



 



 n

k

n  2

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

k n  log

を得る．

第 4 章データの探索

4.1

4.2 2

4.3

ハッシュ法のアイデア

データを格納するおおまかな場所を，そのデータ がもつ情報から決定する．

４０３だから４階 だな

ハッシュ関数

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

例）

x 　 ----> hash(x) = (x の左端の数字）

データを格納するための配列 H

データを格納する場所として，配列 H を準備する

．

ハッシュ法で用いる配列のサイズは格納するデー タのサイズ n の 1.5 ～ 2 倍とするのが一般的で ある．

ここでは， H のサイズは， 1.5n としておく．

ハッシュ法によるデータの格納 の例

hash(x) = (x を 24 で割った余り） = x%24 データの集合

{17, 39, 1, 9, 5,24, 2, 11, 23, 6, 13, 29, 28, 20, 15, 33}

を考える．（ n=16)

データを格納するための配列 H のサイズは 16×1.5 =24

•

アルゴリズム

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 で割った余り ;

アルゴリズム

4.4

入力：アルゴリズム 4.3 によりデータの格納さ れた配列 H と探索する値 x

k = hash(x);

while (H[k] にデータが格納されている ) {

if (H[k] == x) {

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

}

k=((k+1) を m で割ったあまり ;

宿題

第 4 章の演習問題の全て．（提出しなくてもよい

．巻末の解答例を見て自己採点せよ．）

お知らせ

2007 年 12 月 20 日 ( 木）のこの時間帯に中間試験 を行う．詳細は Web ページ

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

に掲載予定です．