アルゴリズムイントロダクション第２章 主にソートに関して 2010年CS勉強会 アルゴリズムイントロダクション第２章 主にソートに関して tniky1 http://www.tniky1.com 12s それでは [マインドマップをベースとした 複数人での情報共有システム ] について発表をはじめます。 発表者は、～です． よろしくお願いします。

本章の目的 「アルゴリズムの設計と解析ってどうやるの？？」って人が大まかな流れ、やり方をつかむ。 簡単なソートでまずはやり方を覚えようってこと Page 2

第２章の内容 ソートアルゴリズム アルゴリズムの正当性 アルゴリズムの実行時間 Θ記法 挿入ソート マージソート ループ不変式 今回は実行時間に違いが現れるこの二つ。 ソートアルゴリズム 挿入ソート マージソート アルゴリズムの正当性 ループ不変式 アルゴリズムの実行時間 Θ記法 Page 3

挿入ソート （まあ、いまさらだろうけど。。） 左から順に挿入しながらソートしていく Page 4

擬似コード procedure Insertion-Sort(A) for j ← 2 to length[A] do key ← A[j] 配列1から 1 2 3 4 5 6 2 5 4 6 1 3 i length[A] procedure Insertion-Sort(A) 　for j ← 2 to length[A] 　　do key ← A[j] 　　　i←j−1 　　　while i > 0 and A[i] > key 　　　　　do A[i+1] ← A[i] 　　　　　i←i−1 　　　A[i+1] ← key Page 5

アルゴリズム作成後の手順 (1)正当性の検証 (2)実行時間を求める 本当にそのアルゴリズムは正しいの？ そのアルゴリズムは有益なの？ まずはこっちから (1)正当性の検証 (2)実行時間を求める Page 6

挿入ソートの正当性 ループ不変式を用いて正当性を示す ループ不変式 A[1...j-1]に格納されているカードはソートされている→ループ不変式として定式化 j 2 5 4 6 1 3 A[1...j-1] ループ中常にソートされている Page 7

ループ不変式を用いたアルゴリズム正当性の示し方 ループ不変式に対して３つの性質を示す 初期条件 ループの実行開始直前でループ不変式が真 ループ内条件 ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真 終了条件 ループが終了した時、アルゴリズムの正当性証明を手助けする有力な情報(今回の場合は配列がソートされていること)が不変式から得られる。 この二つが成り立てば すべてのループの繰り 返しでループ不変式が真 終了時に有力な情報が得られないと意味がない Page 8

ループ不変式でアルゴリズムの正当性を示す j 2 5 4 6 1 3 A[1...j-1] ループ中常にソートされている 　for j ← 2 to length[A] 　　do key ← A[j] 　　　i←j−1 　　　while i > 0 and A[i] > key 　　　　　do A[i+1] ← A[i] 　　　　　i←i−1 　　　A[i+1] ← key 初期条件 J=2 つまりA[1]のみ よってA[1..j-1]はソートされている ループ内条件 A[j]の入れるべき所を探し、見つかるまでA[j-1],A[j-2]...をひとつづつ右にずらし、最後にA[j]を挿入。 各繰り返しでループ不変式が成立(A[1..j-1]はソートされている) Page 9

ループ不変式でアルゴリズムの正当性を示す j=n+1 1 2 3 4 5 6 A[1...j-1]=A[1..n] 　for j ← 2 to length[A] 　　do key ← A[j] 　　　i←j−1 　　　while i > 0 and A[i] > key 　　　　　do A[i+1] ← A[i] 　　　　　i←i−1 　　　A[i+1] ← key 終了条件 j=n+1 つまり A[1..j-1]=A[1..n]はソートされている! よって配列全体がソートされており、 アルゴリズムは正当である Page 10

アルゴリズム作成後の手順 (1)正当性の検証 (2)実行時間を求める 本当にそのアルゴリズムは正しいの？ そのアルゴリズムは有益なの？ 次はこっち。。 (2)実行時間を求める Page 11

アルゴリズムの実行時間を求める 実行時間には下記のようなものがある 通常最悪の場合を考慮すべし！ 最悪時の実行時間 最良時の実行時間 平均実行時間：(確率論が必要で５章で解説) 通常最悪の場合を考慮すべし！ 最悪になる場合が良くあるから(例えば、DB検索のアルゴリズムで検索結果がDBになかったときとか) 最悪の場合を考えておけば、それ以上悪くなることを懸念しなくてすむ Page 12

アルゴリズムの実行時間を求める for j ← 2 to length[A] do key ← A[j] i←j−1 1 2 3 4 5 6 各行の実行回数とその 各実行時間が出れば、 全体の実行時間は求まる！ 2 5 4 6 1 3 i n個 実行回数 　for j ← 2 to length[A] 　　do key ← A[j] 　　　i←j−1 　　　while i > 0 and A[i] > key 　　　　　do A[i+1] ← A[i] 　　　　　i←i−1 　　　A[i+1] ← key n n-1 ループ判定は本体より一回多くなる tj というのは挿入する場所を探す回数 (ループ毎 に異なる) Page 13

アルゴリズムの実行時間を求める for j ← 2 to length[A] do key ← A[j] i←j−1 コスト 実行回数 　for j ← 2 to length[A] 　　do key ← A[j] 　　　i←j−1 　　　while i > 0 and A[i] > key 　　　　　do A[i+1] ← A[i] 　　　　　i←i−1 　　　A[i+1] ← key C1 C2 C3 C4 C5 C6 C7 n n-1 実行時間T(n) つまり、　　　　　が決まれば求めることができる。　　　　　は Page 14

アルゴリズムの実行時間を求める tj=i 実行時間T(n) 挿入する場所を探す回数 (ループ毎 に異なる) [最悪の場合] 　　　　　挿入する場所を探す回数 (ループ毎 に異なる) [最悪の場合] 毎回i=0までソートされる tj=i j 1 2 3 4 5 6 5 6 4 3 2 1 i 最悪の場合逆順で並んでいる 重要なのは実行時間の増加率 上記の式に代入 Page 15

ソートアルゴリズム 挿入ソート マージソート 逐次添加法 分割統治法 部分列を整列した後、一つの要素を新しい場所に挿入することによってソートされた部分列を得る マージソート 分割統治法 問題をいくつかの部分問題に分割し、部分問題を再帰的に解く 特徴として再帰的なアルゴリズムとなる Page 16

マージの動作 番兵 Page 17

マージの擬似コード A 2 4 5 7 1 2 3 6 p q r i j L 2 4 5 7 ∞ R 1 2 3 6 ∞ n1 n2 k 1 2 3 4 5 1 2 3 4 5 L 2 4 5 7 ∞ R 1 2 3 6 ∞ n1 n2 k A 1 2 2 3 4 2 3 6 p q r Page 18

マージの正当性 ループ不変式 Aには、L と R の要素中で小さい方から k − p 個がソートされて入っている L[i] と R[j] は、L と R でまだ A に書き戻さ れていない要素のなかでそれぞれ最小要素である i j 1 2 3 4 5 1 2 3 4 5 L 2 4 5 7 ∞ R 1 2 3 6 ∞ 最小要素 最小要素 k A 1 2 2 3 4 2 3 6 p r ソートされて入っている Page 19

マージの正当性 i j L 2 4 5 7 ∞ R 1 2 3 6 ∞ 最小要素 最小要素 k A 1 2 2 3 4 2 3 6 p r 1 2 3 4 5 1 2 3 4 5 L 2 4 5 7 ∞ R 1 2 3 6 ∞ 最小要素 最小要素 k A 1 2 2 3 4 2 3 6 p r ソートされて入っている 初期条件 k=p つまりA[p..k-1]は空 i=j=1であるのでL,Rは最小の配列要素。よってループ不変式は真 ループ内条件 L[i]<=R[j]と仮定 L[i]がAに戻されていない要素で最小。 L[i]をA[k]にコピーした後にもソートは成り立つ。iとkが１づつインクリメントされるのでL[i],R[j]が最小要素になることも成立。逆も同じ Page 20

マージの正当性 i j L 2 4 5 7 ∞ R 1 2 3 6 ∞ 最小要素 最小要素 k A 1 2 2 3 4 2 3 6 p r 1 2 3 4 5 1 2 3 4 5 L 2 4 5 7 ∞ R 1 2 3 6 ∞ 最小要素 最小要素 k A 1 2 2 3 4 2 3 6 p r ソートされて入っている 終了条件 k=r+1 つまりA[p..k-1]=A[p..r]はソートされている! よって二つの整列した配列からのマージアルゴリズムの正当性は示された 実行時間 「2 つの配列の先頭から小さい方を取る」を n回(n1+n2回)繰り返す: Θ(n) Page 21

マージソート さっきのMERGEを利用してソート ソート列 初期配列 Page 22

マージソートの正当性 配列 A の添字 p から r までをソートする p r A /* (終了条件) */ Page 23

分割統治アルゴリズムの実行時間 問題を a 個の部分問題に分割し、サイズを 1/b にした時 If n <= c とは問題サイズが十分に小さい時 D(n): 分割にかかる時間 C(n): 結合にかかる時間 統治 分割 結合 Page 24

マージソートアルゴリズムの実行時間 T(n) = aT(n/b) + D(n) + C(n) 統治 分割 結合 T(n) = aT(n/b) + D(n) + C(n) 問題を 2 個に分割し、 サイズが 1/2 に なるの で a = b = 2 Merge には Θ(n) 時間かかる 部分列の中央 を計算する だけなので D(n) = Θ(1) T(n) = 2T(n/2) + Θ(1) + Θ(n)　　　 if n > 1 =Θ(1)　　　　　 　　　　　　　　　 if n = 1 これを一般的に解くのは４章で行う。ここではもっと直感的に解く方法を行う。 Page 25

マージソートアルゴリズムの実行時間 最上位レベルの実行時間はcn(マージにかかる時間) Page 26

マージソートアルゴリズムの実行時間 深さがlog2nとなる！ Page 27

まとめ アルゴリズムを書いた時に下記ができると思えればOKかな？ ループ不変式を使用して正当性を示す 実行時間を求める Page 28