今日のアルゴリズム:マージソート、分割当時等
アルゴリズムイントロダクションのメモ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に突っ込む
- 山の最後に特殊な要素∞を用意することで山が空かどうかの確認コストが小さくなる。※でないと比較前に毎度確認の必要あり
- 各山の先頭を比較し、小さいをQueueに追加していく。
- 分割統治の典型的な例
分割統治アルゴリズムの解析
T(n)=\begin{cases} Θ(1) & n \le cの時 \\ aT(n/b)+D(b)+C(n) & それ以外 \end{cases
※hatenablogの仕様で数式を書き直すのが癪だったので修正前のものを残しておく
- マージソートを分割統治アルゴリズムとして解析する
- 分割:分割は部分列の中央を計算するだけだからD(n)=Θ(1)
- 統治:n/2の問題を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)を使うとマージソートのコストはになる
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書
- 作者:Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson
- 出版社/メーカー: 近代科学社
- 発売日: 2018/01/09
- メディア: Kindle版