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

アルゴリズムとデータ構造1
2006年6月16日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html
プログラムとアルゴリズム
• 二分木と言った非線形なデータ構造と,こ
れを扱うアルゴリズム,特に再帰的なアル
ゴリズムについて学ぶ
• つぎにハッシュやソートと言った良く利用さ
れるデータ構造やアルゴリズムの概観を
得る.
Euclidの互除法(2ページ 1.1)
1. mをnで割って、余りをrとする。
2. r=0であれば、アルゴリズムは終了する。
このとき、nが最大公約数である。
3. m←nとする(nの値をmに代入する)。
次にn←rとして1に戻る。
ここでは、次の処理が使われている。
•除算
•0との比較・分岐処理
•変数への代入
•繰り返し(ループ)
/* C言語によるgcdの例1 */
int gcd(int m, int n)
{
int
r;
1: r = m % n;
if (r == 0) goto 2;
m = n;
n = r;
goto 1;
2: return n;
}
/* C言語によるgcdの例2 */
int gcd(int m, int n)
{
int
r;
while((r = m % n) != 0){
m = n;
n = r;
}
return n;
}
/* Java とほとんど同じ */
プログラムは、連接(文の並び順による評価)・条
件分岐(たとえばif文)・繰り返し(例えばwhile文)
だけで構成できるとされている。そもそも、gotoを
使わないで書いたほうがわかりやすいことも多い。
そのような背景で、Javaのようにgotoを使えないプ
ログラミング言語がある。
スタックフレーム
; アセンブリ言語によるgcd関数の例
.text
gcd:
mov.w
@(2,sp),r1
mov.w
@(4,sp),r0
1:
divxu.b r0l,r1
xor.b
r2h,r2h
mov.b
r1h,r2l
beq
2f
mov.w
r0,r1
mov.w
r2,r0
bra
1b
2:
rts
.end
sp+4
; 引数 m
; 引数 n
;
;
;
;
;
;
引数n
sp+2
sp
引数m
戻りアドレス
r = m % n
if(r == 0) goto 2
m = n
n = r
goto 1
return n
簡単なアルゴリズムであればアセンブリ言語
でも記述できる。ただし、アルゴリズムが必要
とする処理をプロセッサが知っていれば…
ちなみに、スタックというデータ構造は、C言
語では例のように、さりげなく使われている。
; アセンブリ言語によるgcd関数の例
.text
gcd:
mov.w @(2,sp),r0
mov.w
@(4,sp),r1
beq
1f
divxu.b r1l,r0
mov.b
r0h,r0l
xor
r0h,r0h
push
r0
push
r1
bsr
gcd
adds.w #2,sp
adds.w #2,sp
1:
rts
.end
スタックフレーム
sp+4
; m
; n
; if (n == 0)
sp+2
sp
引数n
引数m
戻りアドレス
; m % n
bsr直後のスタック
; return m
レジスタ変数r2(変数r)が、不
要になっている。
再帰呼び出しでは、引数は新
しい領域に確保される。新し
い領域としては、スタックが使
われる。
sp+10
引数n
sp+8
引数m
sp+6
戻りアドレス
sp+4
引数n
sp+2
引数m
sp
戻りアドレス
木構造
ルートとそれ以外の
ノードにちょうど1つだけ
の経路しか存在しない
ルートノード
エッジ
ノード
末端ノード
二分木
•各ノードが持てる子
の数が高々2である木
•順序木である
データ
左 右
データ
左 右
データ
左 右
データ
左 右
データ
左 右
データ
左 右
データ
左 右
二分探索木
二分木を次のルールで作成
•親よりも小さい値を持つ子は左
•親よりも大きい値を持つ子は右
29
20
14
7
24
19
21
32
30
31
48
ノードの探索
ノード数をNとすると
O(log N)
の計算量で探索できる
29
20
木が偏っているときは
最悪O(N)になるが…
14
7
24
19
21
32
30
48
31
ハッシュテーブル
データ
データ
キー1
データ
データ
キー2
データ
データ
キー3
データ
ハッシュ関数
データ
分離連鎖法
ハッシュ
テーブル
連結リスト
空き番地法
キー
既にデータが
格納されている
ハッシュ
再ハッシュ
ここも既にデータが
格納されている
再ハッシュ
この場所は空なので
ここに格納する
空き番地法を用いた場合の削除
キー
同じハッシュ値だけ
ど、これじゃない。
ハッシュ
再ハッシュ
削除フラグを格納
削除したい
削除
データは消えてるけ
ど、これでもない。
削除フラグ
再ハッシュ
このデータを
探索したい
これだっ!
整列(ソート)
(145ページ以降で詳しく)
• 配列を使用するソートアルゴリズム
– バブルソート
• 時間計算量O(N2)
– クイックソート
• 時間計算量O(N log N)
• 時間計算量は最悪でもO(N2)
• 空間計算量はいずれもO(N)
バブルソート
10
8 10
8 10
15
10
3 15
15
5 15
32
15
5 15
32
3215
12
32
12
1 32
24
6 24
>
>38 10
<
<
>
>
<
<
>
>
>
>16 >
<
10
38 10
83 10
53 10
15
5 15
12
5 15
32
12
1 15
12
32
61 15
32
61 32
24
6 32
24
入れ替え
入れ替えない
入れ替え
入れ替えない
入れ替え
入れ替えない
入れ替え
入れ替えない
入れ替え
入れ替え
入れ替え
入れ替えない
入れ替え
入れ替え
残りも同様に整列させると…
1
3
5
6
8 10 12 15 24 32
整列済み
クイックソート
基準値を決定
10 8
3 15 5 32 12 1 6 24
基準値を決定
8
3
基準値を決定
基準値を決定
1 6 < 10 < 15 32 12 24
5
基準値を決定
基準値を決定
基準値を決定
整列済み
3
1 < 5 < 8
1 < 3
6
6 < 8
5
1
3
5
6
10
12 < 15 < 32 24
10
12
15
8 10 12 15 24 32
24 < 32
クイック
ソート
32 24 15 12 10 8
6
24 15 12 10 8
5 3
6
15 12 10 8 6 5 3
12 10 8 6 5 3
10 8 6 5 3
8 6 5 3
6 5 3
5 3
3
5 3
1
1 < 32
1 < 24 32
1 < 15 24 32
1 < 12 15 24 32
1 < 10 12 15 24 32
1 < 8 10 12 15 24 32
1 < 6 8 10 12 15 24 32
1 < 5 6 8 10 12 15 24 32
1 < 3 5 6 8 10 12 15 24 32
1
3
5
6
8 10 12 15 24 32