PPT

アルゴリズムとデータ構造1
2008年7月22日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2008/index.html
期末試験
• 教室: C102
• 日時: 2008年7月29日 9時00分～10時30分
– 入室限度: 9時20分まで
– 退出可能: 9時3０分より
• 持ち込み可
– 教科書・資料(自筆・コピー問わず)は持ち込み可
– 人間・パソコン・携帯電話・PHSなど持ち込み不可
• 学生証必携
– 持っていない場合は教務で発行してもらうこと
0
1
ハッシュ
テーブル
103
8, 2
234
6, 1
245
17, 5
2
12
3
13
7
7, 3
47
9, 3
4
14
4
4, 1
44
6, 1
5
15
164
12, 1
71
14, 4
6
16
62
5, 3
81
5, 4
148
15, 2
20
1, 5
72
15, 3
106
11, 4
10
180
9, 5
11
161
9, 4
7
8
9
17
18
98
50
163
5
89
1
28
19
127
81
34
32
78
43
88
117
99
125
100
112
103
186
150
139
154
176
170
180
202
196
244
３. 二分探索木に入れられたデータをルールに基づいて順に参照していく。問
題では中間順で順に参照する。
1, 5, 19, 28, 32, 34, 43, 50, 78, 81, 88, 89, 98, 99, 100, 103, 112, 117,
125, 127, 139, 150, 154, 163, 170, 176, 180, 186, 196, 202, 244
という並びになる。
実は、２番の問題の解答が合ってるかどうかに関係なく、二分探索木の中間
順走査の結果は値の小さい順に並べたデータが出力される。
４. 次のようなことが書かれていればよい。
1. 平衡木とするには、根からすべての葉までの距離が同じでなければいけない。
データの挿入や削除に伴って平衡木を維持できなくなる場合が存在し、そういっ
た場合に木を再構成する。再構成はデータの挿入や削除以外の余分な手間
（オーバーヘッド）なので、少ないほうがいいが、データの偏りはデータの挿入や
削除に要する手間のばらつきとなるため、できれば均一なほうがいい。
2. Ｂ木では、挿入時に枝の数がｍ本を越えたらデータの偏りを防ぐため再構成する
ことにしており、再構成では（ｍ＋１）本の枝を２つの頂点で保持することになる。
つまり、ひとつの頂点あたり（ｍ＋１）/２＝ｍ/２＋１/２ということで、２で割った端
数を切り上げて┌ｍ/２┐になっている。
3. Ｂ木では、削除時にある数を下回ったら按分もしくは頂点の併合を行う。挿入時の
頂点の分割では┌ｍ/２┐を下回らないことから、削除でも┌ｍ/２┐を最小数として
いる。再構成が必要な場合では、２で割った数を切り上げたものより１少ない状態
にあるから、併合してもｍ以下である。大雑把にいえば、挿入の際の再構成の逆
操作である。
4. Ｂ木では、最大数ｍから最小数┌ｍ/２┐の間は再構成しないことにして、性能と平
衡木の定義に合わせたデータ構造の維持のバランスをとっている。
5. Ｂ木では再構成を頂点に再帰的に適用する。根に再構成が及ぶ場合、根の親は
ないので根の分割では、分割後の頂点２つを保持する頂点を設けなくてはならな
い。それが新しい根となり、その瞬間では根からは２本しか枝が出ていない。根か
らの枝の最小数２という制約は、木を根の方向へ生長させることによる。
マージソート
(並列処理)
• データの分割にかかる時間(2要素に分解)
log2n - 1
• ソートにかかる時間
2n - 1
• ステップ数は (log2n + 2n – 2)
つまり O(n)
•
例ではn=16なので34ステップで終了
53 12 41 69 11
2
84 28 31 63 97 58 76 19 91 88
53 69 69
11 84 84
63 97 97
12 53 41 84
2
31 63 58 97 19 88 88
2
28 28
76 91 91
41
69
11
58
91
76
12
53
2
31
88
19
11
41
76
28
63
12
58
11
31
2
19
12 19 28 31 41 53 58 63 69 76 84 88 91 97
パイプラインマージソート
• データの分割にかかる時間(図には書いてない）
log2n - 1
• 最初のデータがソートされる時間
log2n
• 引き続くn-1個のデータがソートされる時間
n-1
• ステップ数は (２ log2n + n-2)
つまりO(n)である
•
例では、n=16 なので22ステップで終了
ソートの計算量
n個のデータの並びは n! とおり存在する
ソートとは、n! の並びのどれであるかを特定すること
1回の比較で並びの可能性が1/2にできる
並びの可能性が1以下にできればソート完了
そのときの比較回数をkとすれば、
すなわち
Stirlingの公式から
およそ n log nという計算量になる
比較を使う限りの性能上限
線形なデータ構造における整列
(ソート)
• 比較によるもの
– バブルソート
– クイックソート
– マージソート
• 比較によらないもの
– ビンソート
計算量を減らす
• 比較を用いたソーティングアルゴリズム
– 大小といった情報は、比較することで得られる
– データの並びについては仮定をおかない
– そうするとO（n log2 n）は下回れない
• 比較を用いないソーティング
– 情報を得なければいけない点は変わらない
– データの性質に合ったアルゴリズムを使う
バブルソートばかりを使うのはやめて、クイッ
クソートのような性能の良いアルゴリズムを
使いましょうという話は間違ってはいない。
ただし、データの性質をも考慮に入れ
てそれが最善かを考える必要はある。
分割統治法(162ページ)
• 元の問題をサイズの小さいいくつかの部
分問題に分割
• 個々の部分問題を何らかの方法で解決
• それらの解を統合することで元の問題の
解を得る
比較を使わないソート
ビンソート
•
•
ビン（瓶ではない、bin = 箱）を使う
データの持つ性質を利用する
–
例:情報の2年生の学生番号（範囲が限られる）
1. ビンをデータの取りうる範囲分確保する
2. データをビンに仕分ける
3. 仕分け完了＝ソート完了なので出力
データは0から8までの範囲であると
いうことが事前にわかっている場合
0から8までのビンを用意する
0
1
2
3
4
5
6
7
8
ビン
7
3
6
0
8
3
2
public final class BinSort
{
public static void sort(int[] anyTargetIntegers, int aMin, int aMax)
{
if(null == anyTargetIntegers){
throw new NullPointerException();
}
BinSort.print(anyTargetIntegers);
int[] bin = new int[aMax - aMin + 1];
for(int i = 0; i < bin.length; i ++){
bin[i] = 0;
}
int[] original = (int [])anyTargetIntegers.clone();
for(int i = 0; i < original.length; i++){
bin[original[i] - aMin]++;
int[] original = new int[anyTargetIntegers.length];
}
for(int i = 0; i < anyTargetIntegers.length; i++){
for(int i = 1; i < bin.length; i ++){
original[i] = anyTargetIntegers[i];
bin[i] += bin[i-1];
}
}
}
}
for(int i = original.length-1; i >= 0; i--){
int j = --bin[original[i] - aMin];
anyTargetIntegers[j] = original[i];
}
BinSort.print(anyTargetIntegers);
public static void print(int[] anyTargetIntegers)
{
int limit = anyTargetIntegers.length - 1;
for(int count = 0; count < limit; count++){
if(10 > anyTargetIntegers[count]){
System.out.print(" ");
}
System.out.print(anyTargetIntegers[count] + ", ");
}
System.out.println(anyTargetIntegers[limit]);
}
[sakai@star 11]$ java BinSortTest
47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88
[sakai@star 11]$
ビンに仕分けて、取り出すだけ。
時間計算量は良い。
空間計算量は良くない。
ハッシュと探索
ソート
比較だけを使用
バブルソート
クイックソート
マージソート
比較以外の方法を使用
ビンソート
探索
比較だけを使用
線形探索
二分探索
 あらかじめソートが必要
比較以外の方法を使用
ハッシュ法

Download Report