今日のアルゴリズム:マージソート､分割当時等

アルゴリズムイントロダクションのメモ2

p24~35まで読了。練習問題は解かない。

• マージソート

  • 分割統治の典型的な例
    • 分割:入力n長の列をn/2の部分列に分割
    • 統治:部分列のソート
    • 結合:マージ
      • MERGE(A,p,q,r)
        • A:配列
        • p,q,r:添字。ただしp<=q<r
          • ソート済みであるA[p...q]とA[q+1...r]の部分文字列を結合し、A[p...r]を作る
        • マージ対象要素数をn=r-q+1とすると計算量Θ(n)
        • 処理内容:※山=部分文字列
          • 各山の先頭を比較し、小さいをQueueに追加していく。
            • 追加しなかった方の先頭と追加した方の先頭を比較→同じように繰り返す
            • どちらかの山が空になった時点で、残りの山を全部queueに突っ込む
              • 山の最後に特殊な要素∞を用意することで山が空かどうかの確認コストが小さくなる。※でないと比較前に毎度確認の必要あり

• 分割統治アルゴリズムの解析

  • サイズnの問題に対するアルゴリズムが再帰呼び出しを含む時、総実行時間をnより小さい数を使った漸化式の形で表現できることが多い。

    • 問題が十分に小さい時(n<=c)は分割せずに解いたほうが早い。この閾値を定数cとする

  • 問題をa個に分割し、部分問題のサイズは元の1/bとする※a=bとならないケースもある

    • 各部分問題のサイズはn/b、サイズはT(n/b)

    • a個の部分問題を解く必要があるので全体はaT(n/b)

    • 分割コストをD(n)、結合コストをC(n)とする

    • T(b)

      • Θ(1) n=1の時
      • aT(n/b)+D(b)+C(n) それ以外​

T(n)=\begin{cases}
    Θ(1) & n \le cの時 \\
    aT(n/b)+D(b)+C(n) & それ以外
\end{cases

※hatenablogの仕様で数式を書き直すのが癪だったので修正前のものを残しておく

• マージソートを分割統治アルゴリズムとして解析する
  • 分割：分割は部分列の中央を計算するだけだからD(n)=Θ(1)
  • 統治:n/2の問題を２つ解く。2*T(n/2)
  • 結合:Θ(n)
  • T(n)
    • Θ(1) n=1の時
    • 2T(n/2)+Θ(n) それ以外​

$$
T(n)=\begin{cases}
   Θ(1) & n = 1 \\
   2T(n/2)+Θ(n) & n > 1
\end{cases}
$$

※ T(n)は再帰的な定義になっていることに注意。

• 上記式をマスター定理(chap4)を使うとマージソートのコストはになる