アルゴリズムとデータ構造1 2005年7月26日 酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html データ構造 • ひとつまたは複数のデータを編成し保持 する構造のこと • データ構造どうしは関連している アルゴリズム • アルゴリズムは必ず問題を解決するもの • ひとつまたは複数のデータを操作し目的 の結果を得るための一連の処理手順 計算量の概念 • アルゴリズムの性能を示す指標 – 時間計算量 • (文字通り)計算に要する時間 – 空間計算量 • どれくらいの作業領域を必要とするかを表す • 大きな問題が少ない計算量で解ければ優秀 – 漸近的に表現したものがO記法 • 計算量を定式化したとき、計算量に最も大きな影響 を及ぼす項をとりだしたもの。 O記法 • 漸近的な振る舞いを表す – 定数項は無視 – 係数は１ – 一般には最も影響力の強い項のみで表す • 項の形で大きく２つに分けられる（問題:n） – 多項式 – 指数関数 ｋ n n k データ構造 線形なデータ構造 配列 リスト 待ち行列(FIFO) リングバッファ スタック(LIFO) 非線形なデータ構造 木 二分探索木 B木 (グラフ) 線形なデータ構造：配列 • 添え字とデータが1対1で対応 • 添え字は連続 1 2 – 添え字が１から始まるとは限らない 3 • データの挿入や削除は面倒 4 … … 添え字を用いてアクセスする（例では３） n データ数nの配列 連結リスト • データをそれぞれの要素に格納 • 要素どおし、つながってリストを形成 先頭 データ データ データ 次 次 次 データを動かすことなく、要素の挿入・削除ができる 待ち行列（FIFO） •連結リストや配列で実装する データ挿入 データ取得 待ち行列（データの挿入・取得） リングバッファ 挿入口 •環状のデータ格納領域 •データの存在を示すポインタ 取り出し口 フロント リア スタック（LIFO） プッシュ ポップ スタックポインタ スタックポインタ スタック構造（プッシュ・ポップ） RPN（逆ポーランド記法） 普通は 1 + 2 と入力して 3 という答えを得ます 同じ答えを得るために、RPNで書くと 1 2 + となります。 普通の書き方の(1 + 2) × (3 + 4) をRPNにすると 1 2 + 3 4 + × となります。 ありがちなプログラミング言語では規則をもとに構文解析を行っている 演算子には優先順位がある 括弧は優先度を変える 変わった言語、変わったプロセッサというものがありまして Forth, PostScriptといった言語、インテル x87 数値演算プロセッサ これらはスタックを基本的なデータ構造としている (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)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要 二分探索 分離連鎖法 ハッシュ テーブル 連結リスト 空き番地法 キー 既にデータが 格納されている ハッシュ 再ハッシュ ここも既にデータが 格納されている 再ハッシュ この場所は空なので ここに格納する 空き番地法を用いた場合の削除 キー 同じハッシュ値だけ ど、これじゃない。 ハッシュ 再ハッシュ 削除フラグを格納 削除したい 削除 データは消えてるけ ど、これでもない。 削除フラグ 再ハッシュ このデータを 探索したい これだっ！ 線形なデータ構造における整列 (ソート) • 比較によるもの – バブルソート – クイックソート – マージソート • 比較によらないもの – ビンソート バブルソート 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 マージソート 手続き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 比較を使わないソート ビンソート • • ビン（瓶ではない、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 非線形なデータ構造：木構造 ルートとそれ以外の ノードにちょうど１つだけ の経路しか存在しない ルートノード エッジ ノード 末端ノード 二分探索木 二分木を次のルールで作成 •親よりも小さい値を持つ子は左 •親よりも大きい値を持つ子は右 29 •バランスの悪い木になることがある 14 7 20 24 19 21 32 30 31 48 二分探索 ノード数をnとすると O(log n) の計算量で探索できる 29 20 木が偏っているときは 最悪O(n)になるが… 14 7 32 24 19 21 30 48 31 B木（B-tree） 二分木ではないが、探索用のｍ分木 いわゆる平衡木 順序木である B木を構成するためのルール 根から葉までの深さはどの葉についても同じである 各頂点（葉以外）の子の数は最大mである 各頂点（葉以外）の子の数は最小 である は切り上げを意味する記号である 根は例外で、最小2である 頂点の構造 頂点にはデータは置かない 探索キーだけをおく キーは枝をたどるときの境目 B木の探索 途中の頂点にはデータは入ってない 入ってる値は部分枝の選択のためのキー値 データは葉の部分におかれている そうしない実装もある 根から部分木を選択しながら下降する 部分木の選択にはO(log m)必要 葉に達したら探索は終了 葉の値と一致すれば成功、そうでなければ失敗 B木の頂点に置く境界値 • 頂点に置かれる値は部分木選択に使われる • 境界値の条件は次の２つを満たす – 左に位置する部分木の最大値以上 – 右に位置する部分木の最小値以下 • 条件を満たす値は複数あるがどれでもいい 境界値 境界値の左部分木 境界値の右部分木 29を探索 3を探索 44を探索 7 7以上31未満の数 7未満の数 3 0 22 6 3 31 6 7 31以上の数 29 22 49 29 31 - - 49 探索失敗 •未満, less than, より小さい •以上, greater than or equal to •以下, less than or equal to 新しいデータ（子）を追加するとき 1. 追加すべき位置（親の頂点）を決定します 2. 親の頂点に空きがあるか調べます 3. 空きがない場合は親の頂点を分割します 親の親の頂点から新たに枝を増やします 親が根である場合は、新たな根を親の親として増やします 4. 子を頂点に追加します データ（子）を削除するとき 1. 削除すべきデータを探索し、削除します 2. 親からの枝の本数が最少数を満たすかどうか調べます 3. 最少数に満たない場合は隣の頂点と子を按分します 按分した結果最少数を満たせない場合は隣の頂点と併合します 親が根である場合に最少数２を割ったら、根を削除します
© Copyright 2024 ExpyDoc
