酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2005年7月26日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html

データ構造 アルゴリズム ひとつまたは複数のデータを編成し保持する構造のこと データ構造どうしは関連している アルゴリズムは必ず問題を解決するもの ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順

計算量の概念 アルゴリズムの性能を示す指標 大きな問題が少ない計算量で解ければ優秀 時間計算量 空間計算量 漸近的に表現したものがO記法 (文字通り)計算に要する時間 空間計算量 どれくらいの作業領域を必要とするかを表す 大きな問題が少ない計算量で解ければ優秀 漸近的に表現したものがO記法 計算量を定式化したとき、計算量に最も大きな影響を及ぼす項をとりだしたもの。

O記法 漸近的な振る舞いを表す 項の形で大きく２つに分けられる（問題:n） 定数項は無視 係数は１ 一般には最も影響力の強い項のみで表す 指数関数　　 kn

データ構造 線形なデータ構造 非線形なデータ構造 配列 リスト 待ち行列(FIFO) スタック(LIFO) 木 (グラフ) リングバッファ 二分探索木 B木 (グラフ)

線形なデータ構造：配列 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 添え字が１から始まるとは限らない 1 2 3 4 n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 添え字を用いてアクセスする（例では３） データ数nの配列

データを動かすことなく、要素の挿入・削除ができる 連結リスト データをそれぞれの要素に格納 要素どおし、つながってリストを形成 先頭 次 データ データを動かすことなく、要素の挿入・削除ができる

待ち行列（FIFO） 連結リストや配列で実装する データ挿入 データ取得 待ち行列（データの挿入・取得）

リングバッファ 挿入口 リア 環状のデータ格納領域 データの存在を示すポインタ 取り出し口 フロント

スタック（LIFO） プッシュ ポップ スタックポインタ スタックポインタ スタックポインタ スタック構造（プッシュ・ポップ）

ありがちなプログラミング言語では規則をもとに構文解析を行っている RPN（逆ポーランド記法） 普通は 1 + 2 と入力して 3 という答えを得ます 同じ答えを得るために、RPNで書くと 1 2 + となります。 普通の書き方の(1 + 2) × (3 + 4) をRPNにすると 1 2 + 3 4 + ×　となります。 ありがちなプログラミング言語では規則をもとに構文解析を行っている 演算子には優先順位がある 括弧は優先度を変える 変わった言語、変わったプロセッサというものがありまして Forth, PostScriptといった言語、インテル x87 数値演算プロセッサ これらはスタックを基本的なデータ構造としている

RPNで記述するとき、日本語で数式の動作を (1 + 2) × (3 + 4) RPNでは 1 2 + 3 4 + (1 + 2) × (3 + 4) ÷(5×6 – 7×8) RPNでは 1 2 + 3 4 + × 5 6 × 7 8 × - ÷ PostScriptでは、三角関数まで定義されている。 GS>1 2 add 3 4 add mul = 21 GS>1 2 add 3 4 add mul 5 6 mul 7 8 mul sub div = -0.807692 GS>30 sin = 0.5 GS>45 cos = 0.707107 RPNで記述するとき、日本語で数式の動作を 読み上げることにかなり近い順序になる

ハノイの塔 一回に一枚の円盤しか動かしてはいけない。 移動の途中で円盤の大小を逆に積んではいけない。 常に大きい方の円盤が下になるようにする。 棒以外のところに円盤を置いてはいけない。 円盤数5のとき、手数は31 nのときは手数2n－1

線形なデータ構造の上における探索 比較によるもの 線形探索 二分探索 比較によらないもの 直接探索 ハッシュ

配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる 直接探索　　　　　　　　　　　　線形探索

配列上の二分探索 半分ずつ調べます 1)半分に分ける 2)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要 二分探索

分離連鎖法 連結リスト ハッシュ テーブル

空き番地法 キー ハッシュ 再ハッシュ 再ハッシュ 既にデータが 格納されている ここも既にデータが 格納されている この場所は空なので ここに格納する

空き番地法を用いた場合の削除 キー 削除 削除したい ハッシュ 再ハッシュ 再ハッシュ 削除フラグを格納 同じハッシュ値だけど、これじゃない。 キー ハッシュ 再ハッシュ データは消えてるけど、これでもない。 削除 削除したい 削除フラグ 削除フラグを格納 再ハッシュ これだっ！ このデータを 探索したい

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

バブルソート ＞ 8 3 ＞ 10 8 ＞ 10 3 ＜ 8 10 ＞ 10 5 ＜ 10 15 ＞ 15 5 ＜ 10 15 ＞ 15 12 ＜ 15 32 ＞ 15 1 ＞ 32 12 ＞ 32 1 ＞ 15 6 ＞ 32 6 ＜ 15 24 ＞ 32 24 整列済み 10 1 8 3 15 5 32 12 6 24 10 8 8 3 10 3 10 5 15 5 15 12 15 1 32 12 32 1 15 6 32 6 24 32 24 入れ替え 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替え 入れ替え 入れ替え 入れ替え 入れ替えない 入れ替え 入れ替え 残りも同様に整列させると… 10 1 8 3 15 5 32 12 6 24

クイックソート 基準値を決定 10 1 8 3 15 5 32 12 6 24 基準値を決定 10 8 3 5 1 6 15 32 12 24 ＜ 10 整列済み 基準値を決定 5 15 ＜ 3 1 8 6 12 32 24 10 5 15 ＜ 3 1 8 6 12 32 24 10 10 1 8 3 15 5 32 12 6 24

マージソート 手続きf(p) 問題pを半分にする それぞれの部分問題に対して次の処理 半分にした問題をマージする 部分問題の要素数が2個 小さい順に並び替える→次の処理へ 部分問題の要素数が1個 並び替える必要が無い→次の処理へ 部分問題の要素数が2個より多い 手続きfを部分問題を引数に呼ぶ 半分にした問題をマージする 部分問題列の先頭から、小さい順に取り出す

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

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

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

非線形なデータ構造：木構造 ルートとそれ以外の ノードにちょうど１つだけ の経路しか存在しない ルートノード 末端ノード エッジ ノード

二分探索木 二分木を次のルールで作成 親よりも小さい値を持つ子は左 親よりも大きい値を持つ子は右 バランスの悪い木になることがある 29 20 32 14 24 30 48 7 19 21 31

二分探索 ノード数をnとすると O(log n) の計算量で探索できる 木が偏っているときは 最悪O(n)になるが… 29 20 32 14 24 30 48 7 19 21 31

B木（B-tree） 二分木ではないが、探索用のｍ分木 いわゆる平衡木 順序木である B木を構成するためのルール 根から葉までの深さはどの葉についても同じである 各頂点（葉以外）の子の数は最大mである 各頂点（葉以外）の子の数は最小 である 　は切り上げを意味する記号である 根は例外で、最小2である

頂点の構造 頂点にはデータは置かない 探索キーだけをおく キーは枝をたどるときの境目

B木の探索 途中の頂点にはデータは入ってない 根から部分木を選択しながら下降する 葉に達したら探索は終了 入ってる値は部分枝の選択のためのキー値 データは葉の部分におかれている そうしない実装もある 根から部分木を選択しながら下降する 部分木の選択にはO(log m)必要 葉に達したら探索は終了 葉の値と一致すれば成功、そうでなければ失敗

B木の頂点に置く境界値 頂点に置かれる値は部分木選択に使われる 境界値の条件は次の２つを満たす 条件を満たす値は複数あるがどれでもいい 左に位置する部分木の最大値以上 右に位置する部分木の最小値以下 条件を満たす値は複数あるがどれでもいい 境界値 境界値の左部分木 境界値の右部分木

44を探索 3を探索 29を探索 探索失敗 7未満の数 7以上31未満の数 31以上の数 未満, less than, より小さい 6 22 29 - 49 3 6 7 22 29 31 49 探索失敗 未満, less than, より小さい 以上, greater than or equal to 以下, less than or equal to

新しいデータ（子）を追加するとき 追加すべき位置（親の頂点）を決定します 親の頂点に空きがあるか調べます 空きがない場合は親の頂点を分割します 親の親の頂点から新たに枝を増やします 親が根である場合は、新たな根を親の親として増やします 子を頂点に追加します

データ（子）を削除するとき 削除すべきデータを探索し、削除します 親からの枝の本数が最少数を満たすかどうか調べます 最少数に満たない場合は隣の頂点と子を按分します 按分した結果最少数を満たせない場合は隣の頂点と併合します 親が根である場合に最少数２を割ったら、根を削除します