2010年CS勉強会 アルゴリズムイントロダクション第２章 主にソートに関して tniky1 http://www.tniky1.com 2010年CS勉強会：アルゴリズムイントロダクション 本章の目的 「アルゴリズムの設計と解析ってどうやるの？？」って人 が大まかな流れ、やり方をつかむ。 簡単なソートでまずはやり方を覚えようってこと Copyright© 2010 tniky1 All rights reserved. Page 2 2010年CS勉強会：アルゴリズムイントロダクション 第２章の内容 ソートアルゴリズム 今回は実行時間に違いが現れるこの二つ。 - 挿入ソート - マージソート アルゴリズムの正当性 - ループ不変式 アルゴリズムの実行時間 - Θ記法 Copyright© 2010 tniky1 All rights reserved. Page 3 2010年CS勉強会：アルゴリズムイントロダクション 挿入ソート （まあ、いまさらだろうけど。。） 左から順に挿入しながらソートしていく Copyright© 2010 tniky1 All rights reserved. Page 4 2010年CS勉強会：アルゴリズムイントロダクション 擬似コード 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 Copyright© 2010 tniky1 All rights reserved. Page 5 2010年CS勉強会：アルゴリズムイントロダクション アルゴリズム作成後の手順 本当にそのアルゴリズムは正しいの？ そのアルゴリズムは有益なの？ まずはこっちから (1)正当性の検証 (2)実行時間を求める Copyright© 2010 tniky1 All rights reserved. Page 6 2010年CS勉強会：アルゴリズムイントロダクション 挿入ソートの正当性 ループ不変式を用いて正当性を示す ループ不変式 - A[1...j-1]に格納されているカードはソートされている→ループ不変式として 定式化 j 2 5 4 6 1 3 A[1...j-1] ループ中常にソートされている Copyright© 2010 tniky1 All rights reserved. Page 7 2010年CS勉強会：アルゴリズムイントロダクション ループ不変式を用いたアルゴリズム正当性の示し方 ループ不変式に対して３つの性質を示す - 初期条件 - ループの実行開始直前でループ不変式が真 この二つが成り立てば すべてのループの繰り 返しでループ不変式が真 - ループ内条件 - ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰 り返しの直前でも真 - 終了条件 - ループが終了した時、アルゴリズムの正当性証明を手助けする有力な情 報(今回の場合は配列がソートされていること)が不変式から得られる。 終了時に有力な情報が得られないと意味がない Copyright© 2010 tniky1 All rights reserved. Page 8 2010年CS勉強会：アルゴリズムイントロダクション ループ不変式でアルゴリズムの正当性を示す 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 Copyright© 2010 tniky1 All rights reserved. 初期条件 J=2 つまりA[1]のみ よってA[1..j-1]はソートされている ループ内条件 A[j]の入れるべき所を探し、見つか るまでA[j-1],A[j-2]...をひとつづつ右 にずらし、最後にA[j]を挿入。 各繰り返しでループ不変式が成立 (A[1..j-1]はソートされている) Page 9 2010年CS勉強会：アルゴリズムイントロダクション ループ不変式でアルゴリズムの正当性を示す 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 Copyright© 2010 tniky1 All rights reserved. 終了条件 j=n+1 つまり A[1..j-1]=A[1..n]はソートされている ! よって配列全体がソートされており、 アルゴリズムは正当である Page 10 2010年CS勉強会：アルゴリズムイントロダクション アルゴリズム作成後の手順 本当にそのアルゴリズムは正しいの？ そのアルゴリズムは有益なの？ (1)正当性の検証 次はこっち。。 (2)実行時間を求める Copyright© 2010 tniky1 All rights reserved. Page 11 2010年CS勉強会：アルゴリズムイントロダクション アルゴリズムの実行時間を求める 実行時間には下記のようなものがある - 最悪時の実行時間 - 最良時の実行時間 - 平均実行時間：(確率論が必要で５章で解説) 通常最悪の場合を考慮すべし！ - 最悪になる場合が良くあるから(例えば、DB検索のアルゴリズム で検索結果がDBになかったときとか) - 最悪の場合を考えておけば、それ以上悪くなることを懸念しなく てすむ Copyright© 2010 tniky1 All rights reserved. Page 12 2010年CS勉強会：アルゴリズムイントロダクション アルゴリズムの実行時間を求める j 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 Copyright© 2010 tniky1 All rights reserved. n n-1 n-1 ループ判定は本体 より一回多くなる tj というのは挿入する n-1 場所を探す回数 (ル ープ毎 に異なる) Page 13 2010年CS勉強会：アルゴリズムイントロダクション アルゴリズムの実行時間を求める コスト 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 n-1 n-1 実行時間T(n) つまり、 が決まれば求めることができる。 Copyright© 2010 tniky1 All rights reserved. は Page 14 2010年CS勉強会：アルゴリズムイントロダクション アルゴリズムの実行時間を求める 実行時間T(n) 挿入する場所を探す回数 (ループ毎 に異なる) j 1 2 3 [最悪の場合] 毎回i=0までソートされる tj=i 4 5 6 5 6 4 3 2 1 i 最悪の場合逆順で並んでいる 上記の式に代入 Copyright© 2010 tniky1 All rights reserved. 重要なのは実行時間の増加率 Page 15 2010年CS勉強会：アルゴリズムイントロダクション ソートアルゴリズム 挿入ソート - 逐次添加法 - 部分列を整列した後、一つの要素を新しい場所に挿入することによって ソートされた部分列を得る マージソート - 分割統治法 - 問題をいくつかの部分問題に分割し、部分問題を再帰的に解く - 特徴として再帰的なアルゴリズムとなる Copyright© 2010 tniky1 All rights reserved. Page 16 2010年CS勉強会：アルゴリズムイントロダクション マージの動作 番兵 Copyright© 2010 tniky1 All rights reserved. Page 17 2010年CS勉強会：アルゴリズムイントロダクション マージの擬似コード A 2 4 5 7 1 2 3 6 p q j i 1 2 3 r 4 1 2 3 5 4 5 R 1 2 3 6 ∞ L 2 4 5 7 ∞ n2 n1 k A 1 2 2 3 4 2 3 6 p q r Copyright© 2010 tniky1 All rights reserved. Page 18 2010年CS勉強会：アルゴリズムイントロダクション マージの正当性 ループ不変式 - Aには、L と R の要素中で小さい方から k − p 個がソートされて 入っている - L[i] と R[j] は、L と R でまだ A に書き戻さ れていない要素のな かでそれぞれ最小要素である j i 1 2 3 4 L 2 4 5 7 ∞ 最小要素 1 2 3 5 4 5 R 1 2 3 6 ∞ k 最小要素 A 1 2 2 3 4 2 3 6 p r ソートされて入っている Copyright© 2010 tniky1 All rights reserved. Page 19 2010年CS勉強会：アルゴリズムイントロダクション マージの正当性 j i 1 2 3 4 L 2 4 5 7 ∞ 最小要素 1 2 3 5 4 5 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]が最 小要素になることも成立。逆も同じ Copyright© 2010 tniky1 All rights reserved. Page 20 2010年CS勉強会：アルゴリズムイントロダクション マージの正当性 j i 1 2 3 4 L 2 4 5 7 ∞ 最小要素 1 2 3 5 4 5 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) Copyright© 2010 tniky1 All rights reserved. Page 21 2010年CS勉強会：アルゴリズムイントロダクション マージソート さっきのMERGEを利用してソート ソート列 初期配列 Copyright© 2010 tniky1 All rights reserved. Page 22 2010年CS勉強会：アルゴリズムイントロダクション マージソートの正当性 配列 A の添字 p から r までをソートする p r A /* (終了条件) */ Copyright© 2010 tniky1 All rights reserved. Page 23 2010年CS勉強会：アルゴリズムイントロダクション 分割統治アルゴリズムの実行時間 - 問題を a 個の部分問題に分割し、サイズを 1/b にした時 統治 分割 結合 - If n <= c とは問題サイズが十分に小さい時 - D(n): 分割にかかる時間 - C(n): 結合にかかる時間 Copyright© 2010 tniky1 All rights reserved. Page 24 2010年CS勉強会：アルゴリズムイントロダクション マージソートアルゴリズムの実行時間 統治 分割 結合 T(n) = aT(n/b) + D(n) + C(n) 問題を 2 個に分割し、 サイズが 1/2 に なるの でa=b=2 部分列の中央 を計算する だけなので D(n) = Θ(1) T(n) = 2T(n/2) + Θ(1) + Θ(n) =Θ(1) Merge には Θ(n) 時間かかる if n > 1 if n = 1 これを一般的に解くのは４章で行う。ここではもっと直感的に解く方法を行う。 Copyright© 2010 tniky1 All rights reserved. Page 25 2010年CS勉強会：アルゴリズムイントロダクション マージソートアルゴリズムの実行時間 最上位レベルの実行時間はcn(マージにかかる時間) Copyright© 2010 tniky1 All rights reserved. Page 26 2010年CS勉強会：アルゴリズムイントロダクション マージソートアルゴリズムの実行時間 深さがlog2nとなる！ Copyright© 2010 tniky1 All rights reserved. Page 27 2010年CS勉強会：アルゴリズムイントロダクション まとめ アルゴリズムを書いた時に下記ができると思えればOK かな？ - ループ不変式を使用して正当性を示す - 実行時間を求める Copyright© 2010 tniky1 All rights reserved. Page 28
© Copyright 2024 ExpyDoc
