誰にも見えないブログ

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

今日のアルゴリズム:置き換え法を使った漸化式の計算量の推定

algorithm 勉強メモ

アドホックで役に立たなさそうな気がする｡次の再帰木やマスター定理が本命か｡

置き換え法

  • 漸化式のコストを示すことが目的

  • substituion method

  • 手順

    • 1.解の形を推定する
    • 数学的帰納法を用いて定数を求め､推定した解がうまく働くことを示す｡
  • 特徴
    • 解の形が推定できる場合にしか適応できない
    • 上階下界どちらの証明にも利用可能
  • 例: T(n)=2T(\lfloor{n/2}\rfloor)+nの上界を求める
    • T(n)=O(n\lg n)であると推定し､これを検証する
    • 任意の定数c>0に対して T(n) \leq cn\lg nであることを証明する
      • \lfloor n/2 \rfloorで成立を仮定すると T(\lfloor n/2 \rfloor) \leq c \lfloor n/2 \rfloor \lg (\lfloor n/2 \rfloor ) である
        • 漸化式に代入し不等式を求める
          • T(n) \leq 2(c \lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor ) + n
          • \leq cn \lg(n/2) + n
          • =cn \lg n - cn\lg 2+n
          • =cn\lg n -cn + n
          • \leq cn\lg n
      • 上記より T(n) \leq cn \lg nを示すことができた｡
    • 数学的帰納法ではこの解が境界条件を満たすことを示す必要がある｡
      • ※補足:この漸化式 T(n)=2T(\lfloor{n/2}\rfloor)+nは境界条件が与えられていないので､仮定する必要がある｡
      • 境界条件を T(1)=1であると仮定する

境界条件を保持しつつ基底の崩壊を防ぐ方法

  • 漸近記法の特徴を活かす
    • 任意の n \geq n_0に対して T(n) \leq cn \lg nが証明できれば十分
  • 境界条件T(1)=1は保持する
  • n_0=2とし､帰納的証明の基底にT(2),T(3)を用いる
    • ※漸化式の基底(n=1)と機能的証明の基底(n=2,3)の区別に注意｡
    • T(2)=4,T(3)=5である(筆算で確認済み)
      • 以下を成立させる適当な大きさcがあれば c \geq 1に対して T(n) \leq cn \lg nであることの証明が完了する
        • T(2) \leq c2 \lg 2
        • T(3) \leq c3 \lg 3
      • 上記2不等式は c \geq 2なものを選べば成立する。

推定のコツ

  • 大前提
    • 推定の一般的な方法は存在しない→勘と経験
    • ただしいくつかコツはある｡
  • 以前に扱った似た解を推定する
  • 漸化式の弱い上界､下界を証明し､次第に範囲を減らしていく
    • 漸化式 T(n) = 2T(\lfloor n/2 \rfloor ) + nの場合
      • 弱い初期値
        • 下界: T(n)=Ω(n)
        • 上界: T(n)=O(n^2)
      • 上記を少しずつ狭めていき正しい漸近解 T(n)=θ(n \lg n)を求める

アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書

アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書