誰にも見えないブログ

雑なメモ。まとまってない文章等

今日のアルゴリズム:分割統治,最大部分配列問題

CS勉強するのは割に合わないとかいってる舌の根も乾かぬうちにアルゴリズムを勉強していく回です。

分割統治

  • 概要
    • 分割:問題のサイズを分ける
    • 統治:分けた問題を再帰的に解く
    • 結合:部分問題を結合し元の問題の解を得る
  • 直接解いた方が早い場合は直接問題を解く
  • 再起段階:部分問題に分割して再帰的に解いた方が良い問題規模のこと
  • 基底:分割問題をこれ以上再帰処理する必要がない程度に小さいサイズのこと。

漸化式

  • ”ある入力に対する関数値をそれより小さな愛入力に対する関数値を用いて記述する等式又は不等式”(p54)
  • 分割統治と協力関係にある
  • 例:マージソートの場合
    • T(n)
      • =Θ(1):n=1の時
      • =2T(n/2)+Θ(n):n>1のとき
  • 漸化式の漸近的限界を得る方法
    • 置き換え方(substitution method)
    • 再帰木法 (recursion-tree method)
      • 再帰の各段階コストを表現できる木構造に漸化式を変換し、和の上界、又は下界を求める
    • マスター法(master method)
      • T(n)=aT(n/b)+f(n)ただしa \geq 1, b >1形式の漸化式に限界を与える
        • ※分割数=a、部分問題のサイズ=b
      • 3通りの場合分け
        • 用加筆

最大部分配列問題

  • 配列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^2)
      • Θ(n^2)個の部分配列を調べる必要がある
        • (n-1)!な気がするが...
      • 部分配列の計算は配列の長さに比例した時間が必要だが、一度計算した結果を再利用することでΘ(1)で計算することができる
      • よって総当たりを行えばΘ(n^2)となる。
        • ※負数を要素に含まない配列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]の中にある
      • 中央点をまたいで存在している
  • 中央点をまたいで存在している場合の解決法
    • 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]もほぼ同手順)
  • 全体のアルゴリズム

    • 配列を2分割して上記中央点を..のアルゴリズムと全体のアルゴリズム再帰的に適応していく。
      • 最終的に2分割した部分配列中の最大部分配列と中央点を含む最大部分配列が求まるので3つの中で大きい方を結果とする。
    • この書き方はかなり説明不足なので本を確認。
  • 例:

    • ※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)=Θ(n lg n)

続く...