酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2008年7月22日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) 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など持ち込み不可 学生証必携 持っていない場合は教務で発行してもらうこと

ハッシュ テーブル 103 8, 2 1 234 6, 1 2 245 17, 5 12 3 7 7, 3 47 9, 3 13 4 14 4 4, 1 44 6, 1 5 15 164 12, 1 71 14, 4 6 16 62 5, 3 81 5, 4 7 17 148 15, 2 20 1, 5 8 18 72 15, 3 106 11, 4 9 180 9, 5 10 11 161 9, 4

98 50 163 5 89 127 186 1 28 81 117 150 176 202 19 34 78 88 99 125 139 154 170 180 196 244 32 43 100 112 103

３. 二分探索木に入れられたデータをルールに基づいて順に参照していく。問題では中間順で順に参照する。 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 という並びになる。 実は、２番の問題の解答が合ってるかどうかに関係なく、二分探索木の中間順走査の結果は値の小さい順に並べたデータが出力される。

４. 次のようなことが書かれていればよい。 平衡木とするには、根からすべての葉までの距離が同じでなければいけない。データの挿入や削除に伴って平衡木を維持できなくなる場合が存在し、そういった場合に木を再構成する。再構成はデータの挿入や削除以外の余分な手間（オーバーヘッド）なので、少ないほうがいいが、データの偏りはデータの挿入や削除に要する手間のばらつきとなるため、できれば均一なほうがいい。 Ｂ木では、挿入時に枝の数がｍ本を越えたらデータの偏りを防ぐため再構成することにしており、再構成では（ｍ＋１）本の枝を２つの頂点で保持することになる。つまり、ひとつの頂点あたり（ｍ＋１）/２＝ｍ/２＋１/２ということで、２で割った端数を切り上げて┌ｍ/２┐になっている。 Ｂ木では、削除時にある数を下回ったら按分もしくは頂点の併合を行う。挿入時の頂点の分割では┌ｍ/２┐を下回らないことから、削除でも┌ｍ/２┐を最小数としている。再構成が必要な場合では、２で割った数を切り上げたものより１少ない状態にあるから、併合してもｍ以下である。大雑把にいえば、挿入の際の再構成の逆操作である。 Ｂ木では、最大数ｍから最小数┌ｍ/２┐の間は再構成しないことにして、性能と平衡木の定義に合わせたデータ構造の維持のバランスをとっている。 Ｂ木では再構成を頂点に再帰的に適用する。根に再構成が及ぶ場合、根の親はないので根の分割では、分割後の頂点２つを保持する頂点を設けなくてはならない。それが新しい根となり、その瞬間では根からは２本しか枝が出ていない。根からの枝の最小数２という制約は、木を根の方向へ生長させることによる。

マージソート (並列処理) データの分割にかかる時間(2要素に分解) log2n - 1 ソートにかかる時間 2n - 1 ステップ数は (log2n + 2n – 2) つまり O(n) 　　　例ではn=16なので34ステップで終了

69 11 84 63 76 91 53 97 41 2 28 31 58 19 12 88 53 69 69 11 84 84 63 97 97 76 91 91 12 53 41 84 2 28 28 31 63 58 97 19 88 88 41 69 11 58 91 76 12 53 2 31 88 19 41 76 28 63 12 58 11 31 2 19 2 11 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! とおり存在する 1回の比較で並びの可能性が1/2にできる 並びの可能性が1以下にできればソート完了 そのときの比較回数をkとすれば、 すなわち Stirlingの公式から およそ n log nという計算量になる 比較を使う限りの性能上限

線形なデータ構造における整列(ソート) 比較によるもの バブルソート クイックソート マージソート 比較によらないもの ビンソート

計算量を減らす 比較を用いたソーティングアルゴリズム 比較を用いないソーティング 大小といった情報は、比較することで得られる データの並びについては仮定をおかない そうするとO（n log2 n）は下回れない 比較を用いないソーティング 情報を得なければいけない点は変わらない データの性質に合ったアルゴリズムを使う バブルソートばかりを使うのはやめて、クイックソートのような性能の良いアルゴリズムを使いましょうという話は間違ってはいない。 ただし、データの性質をも考慮に入れてそれが最善かを考える必要はある。

分割統治法(162ページ) 元の問題をサイズの小さいいくつかの部分問題に分割 個々の部分問題を何らかの方法で解決 それらの解を統合することで元の問題の解を得る

比較を使わないソート ビンソート ビン（瓶ではない、bin = 箱）を使う データの持つ性質を利用する ビンをデータの取りうる範囲分確保する 例:情報の2年生の学生番号（範囲が限られる） ビンをデータの取りうる範囲分確保する データをビンに仕分ける 仕分け完了＝ソート完了なので出力

データは0から8までの範囲であるということが事前にわかっている場合 0から8までのビンを用意する 1 2 3 4 7 3 6 8 3 2 5 6 7 8 ビン

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]++; for(int i = 1; i < bin.length; 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]; int[] original = new int[anyTargetIntegers.length]; for(int i = 0; i < anyTargetIntegers.length; i++){ original[i] = anyTargetIntegers[i]; }

ビンに仕分けて、取り出すだけ。 時間計算量は良い。 空間計算量は良くない。 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]$ ビンに仕分けて、取り出すだけ。 時間計算量は良い。 空間計算量は良くない。

ハッシュと探索 ソート 探索 比較だけを使用 比較以外の方法を使用 比較だけを使用 比較以外の方法を使用 バブルソート クイックソート マージソート 比較以外の方法を使用 ビンソート 探索 比較だけを使用 線形探索 二分探索 あらかじめソートが必要 比較以外の方法を使用 ハッシュ法