アルゴリズムとデータ構造1 2006年6月16日酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html プログラムとアルゴリズム • 二分木と言った非線形なデータ構造と，これを扱うアルゴリズム，特に再帰的なアルゴリズムについて学ぶ • つぎにハッシュやソートと言った良く利用されるデータ構造やアルゴリズムの概観を得る．Ｅｕｃｌｉｄの互除法（２ページ 1.1） 1. ｍをｎで割って、余りをｒとする。 2. ｒ＝０であれば、アルゴリズムは終了する。このとき、ｎが最大公約数である。 3. ｍ←ｎとする（ｎの値をｍに代入する）。次にｎ←ｒとして１に戻る。ここでは、次の処理が使われている。 •除算 •０との比較・分岐処理 •変数への代入 •繰り返し（ループ） /* 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 ｓｐ＋４ ; 引数 m ; 引数 n ; ; ; ; ; ; 引数ｎｓｐ＋２ｓｐ引数ｍ戻りアドレス r = m % n if(r == 0) goto 2 m = n n = r goto 1 return n 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、Ｃ言語では例のように、さりげなく使われている。 ; アセンブリ言語による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 スタックフレームｓｐ＋４ ; m ; n ; if (n == 0) ｓｐ＋２ｓｐ引数ｎ引数ｍ戻りアドレス ; m % n ｂｓｒ直後のスタック ; return m レジスタ変数r2(変数r)が、不要になっている。再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。ｓｐ＋１０引数ｎｓｐ＋８引数ｍｓｐ＋６戻りアドレスｓｐ＋４引数ｎｓｐ＋２引数ｍｓｐ戻りアドレス木構造ルートとそれ以外のノードにちょうど１つだけの経路しか存在しないルートノードエッジノード末端ノード二分木 •各ノードが持てる子の数が高々２である木 •順序木であるデータ左右データ左右データ左右データ左右データ左右データ左右データ左右二分探索木二分木を次のルールで作成 •親よりも小さい値を持つ子は左 •親よりも大きい値を持つ子は右 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 ハッシュテーブルデータデータキー１データデータキー２データデータキー３データハッシュ関数データ分離連鎖法ハッシュテーブル連結リスト空き番地法キー既にデータが格納されているハッシュ再ハッシュここも既にデータが格納されている再ハッシュこの場所は空なのでここに格納する空き番地法を用いた場合の削除キー同じハッシュ値だけど、これじゃない。ハッシュ再ハッシュ削除フラグを格納削除したい削除データは消えてるけど、これでもない。削除フラグ再ハッシュこのデータを探索したいこれだっ！整列（ソート） (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