アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2010年7月22日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html
x
h(x)
h(x)+g(x)
12
12
12
22
22
22
7
7
7
4
4
4
62
16
16
39
16
29
6
6
87
18
18
31
8
8
44
21
21
71
2
2
20
20
20
67
21
16+3=19
21+3=24
ハッシュ表中の位置
19
1
最小の子の数は２
最大の子の数は３
問題のB木
５７を追加
７を追加
最大の子の数は３というルールがあるので、
木を根のほうに向かって成長させる。
８４を削除
５８を削除
最小の子の数は２というルールがあるので、
木を根のほうから刈り込む。
７５を削除
マージソート
(並列処理)
• データの分割にかかる時間(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 = 1; i < bin.length; i ++){ for(int i = 0; i < anyTargetIntegers.length; i++){
bin[i] += bin[i-1];
original[i] = anyTargetIntegers[i];
}
}
}
}
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