今日のアルゴリズム:分割統治,最大部分配列問題
CS勉強するのは割に合わないとかいってる舌の根も乾かぬうちにアルゴリズムを勉強していく回です。
分割統治
- 概要
- 分割:問題のサイズを分ける
- 統治:分けた問題を再帰的に解く
- 結合:部分問題を結合し元の問題の解を得る
- 直接解いた方が早い場合は直接問題を解く
- 再起段階:部分問題に分割して再帰的に解いた方が良い問題規模のこと
- 基底:分割問題をこれ以上再帰処理する必要がない程度に小さいサイズのこと。
漸化式
- ”ある入力に対する関数値をそれより小さな愛入力に対する関数値を用いて記述する等式又は不等式”(p54)
- 分割統治と協力関係にある
- 例:マージソートの場合
- T(n)
- :n=1の時
- :n>1のとき
- T(n)
- 漸化式の漸近的限界を得る方法
最大部分配列問題
- 配列A[1 .. n]のうちA[i .. j]間の要素の和が最大となるi,jを求める問題
- 例:
A=[13,−3,−25,20,−3,−16,−23,18,20,−7,12,−5,−22,15,−4,7]
A[8 .. 11]=[18,20,-7,12]
が43で最大
- 総当たりの計算量:
- 個の部分配列を調べる必要がある
- (n-1)!な気がするが...
- 部分配列の計算は配列の長さに比例した時間が必要だが、一度計算した結果を再利用することでΘ(1)で計算することができる
- よって総当たりを行えばとなる。
- ※負数を要素に含まない配列
A[1 .. n]
の場合最大部分配列はA[1 .. n]
そのものになる
- ※負数を要素に含まない配列
- 個の部分配列を調べる必要がある
- 例:
分割統治で解く
- A[low .. high]を2つに分割する
- 中央点mid
- A[low .. mid]
- A[mid + 1 .. high]
- このとき、最大部分配列A[i .. j]は以下のどこかにある
- A[low .. mid]の中にある
- A[mid +1 .. mid]の中にある
- 中央点をまたいで存在している
- 中央点mid
- 中央点をまたいで存在している場合の解決法
- A[low ... mid ... high]をmidで分割できる二つの部分配列に対する最大部分配列の結合を求めることで解く
- 手順
- midで分割する
- 前半:A[low .. mid]内でmidで終わる最大部分配列A[i .. mid]を求める
- 後半:A[mid +1 ... high]内でmid+1から始まる最大部分配列A[mid +1 .. j]を求める
- 分割したインスタンスの最大部分配列の求め方
- 前半:A[low .. mid]のみ解説
- mid~lowのforループで各要素を合算し、ループ内最後で合算が今まで最高になったindexとその最大値を記録する
- ループ終了後に合算が最大になったindex iが求まるのでそれをA[i .. mid]とする(分割の後半要素A[mid +1 .. j]もほぼ同手順)
- 前半:A[low .. mid]のみ解説
全体のアルゴリズム
例:
- ※2分割した部分配列の前半をL(left)後半をR(right) 、中間点を含む最大部分配列をM(middle)とした
- 各ループ中で3配列中最大の合計を持つものにチェックを入れている。
A=[13,−3,−25,20,−3,−16,−23,18,20,−7,12,−5,−22,15,−4,7]
L=[13,−3,−25,20,−3,−16,−23,18]=20
☑️LL[13,−3,−25,20]=20
LLL[13,-3]=13
☑️LLLL[13]=13
LLLR[-3]=-3
LLLM[13,-3]=10
☑️LLR[-25,20]=20
- ループ内略
LLM[13,−3,−25,20]=[13,-3,-15]=-25
- ループ内略
LR[−3,−16,−23,18]=18
- ループ内略
LM[13,−3,−25,20,−3,−16,−23,18]=[20,-3]=17
R=[20,−7,12,−5,−22,15,−4,7]=20
☑️MID[13,−3,−25,20,−3,−16,−23,18,20,−7,12,−5,−22,15,−4,7]=[18,20,-7,12]=43
MIDL[18]=18
MIDR[20,-7,12]=25
計算量
- 漸化式
- T(n)=Θ(1)+2T(n/2)+Θ(n)+Θ(1)
- =2T(n/2)+Θ(n)
- T(n)=Θ(1)+2T(n/2)+Θ(n)+Θ(1)
- 漸化式の解(マスター法)
- T(n)=Θ(n lg n)
- 漸化式
続く...
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書
- 作者:Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson
- 出版社/メーカー: 近代科学社
- 発売日: 2018/01/09
- メディア: Kindle版