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

アルゴリズムとデータ構造1
2007年7月17日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2007/index.html
期末試験
• 教室: K101
• 日時: 2007年7月27日 10時40分～12時10分
– 入室限度: 11時00分まで
– 退出可能: 11時1０分より
• 持ち込み可
– 教科書・資料(自筆・コピー問わず)は持ち込み可
– 人間・パソコン・携帯電話・PHSなど持ち込み不可
• 学生証必携
– 持っていない場合は教務で発行してもらうこと
マージソート(198ページ)
手続きf(p)
• 問題pを半分にする
それぞれの部分問題に対して次の処理
– 部分問題の要素数が2個
• 小さい順に並び替える→次の処理へ
– 部分問題の要素数が1個
• 並び替える必要が無い→次の処理へ
– 部分問題の要素数が2個より多い
• 手続きfを部分問題を引数に呼ぶ
• 半分にした問題をマージする
– 部分問題列の先頭から、小さい順に取り出す
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
マージソート
(逐次処理, 201ページ)
• データの分割にかかる時間(2要素に分解)
n/2
• ソートにかかる時間(段数log2n, データ数n)
n log2n
• ステップ数は n/2 + n log2n
つまり O(n log2n)
•
クイックソートと並ぶオーダーで処理ができる
マージソート
(並列処理)
• データの分割にかかる時間(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