誰にも見えないブログ

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

今日のアルゴリズム:再帰木を使ったアルゴリズムのコスト推定(計算)

algorithm book 勉強メモ

数学弱者なので対数やsumをうまく簡単な数式に変換することが出来ない｡(悲)

再帰木

  • 部分問題の再帰呼び出しを木で図示しレベルごとのコスト､全体のコストを考えることができる

  • 再帰木によるコストの推定→置き換え法によるコスト検証という流れでアルゴリズムを分析できる

    • 後続に検証ステップがあるので多少の杜撰さは許される
      • 厳密に再帰木を書くなら証明にも利用可能

  • 例:T(n)=3T(\lfloor n/4 \rfloor) + θ(n^2)

    • 床関数･天井関数のコストは無視できる(許容できる杜撰さ)

    • T(n)=3T(n/4) + cn^2にたいして再帰木を構成する

      • 仮定:部分問題のサイズが整数になるようにnは4の冪乗と仮定する

    • 再帰木の深さ

      • 部分問題のnのサイズはn,n/4,n/16,...n/4^iという具合に再帰のレベルiが深くなるごとに小さくなっていく
        • 部分問題のサイズ=1が境界条件だとするとn/4^i=1のレベルiが再帰レベルの深さの限界になる
        • i=\log_4{n}となる
        • 再帰木は\log_4{n}+1の高さを持つ

    • 再帰木の各レベルのコスト

      • 部分問題の各レベルの総数は1,3,9,...,3^iという具合に再帰のレベルiが深くなるにつれ増加していく
      • 部分問題のサイズは上述のとおりc(n/4^i)^2である
        • 階層iの部分問題の総コストは3^i*c(n/4^i)^2=(3/16)^icn^2
        • 底のレベルには接点が3^{\log_4{n}}=n^{\log_4{3}}個の接点があり､部分問題のコストはT(1)である
          • 底のコストはθ(n^{log_4{3}})となる

    • 木全体のコスト

      • T(n)=cn^2+\frac{3}{16}cn^2 + (\frac{3}{16})^{2}cn^2 + \cdots + (\frac{3}{16})^{\log_4{n-1}}cn^2 + θ(n^{\log_4{3}})
      • =\sum_{i=3}^{\log_4{n-1}}(\frac{3}{16})^icn^2+θ(n^{\log_4{3}})
      • =\frac{(3/16)^{\log_4n}-1}{(3/16)-1}cn^2 + θ(n^{\log_4{3}}) ※幾何級数に対する規則(A.5)の変形を使っている
        • (補足p951和の公式と性質より)A.5:\sum^n_{k=0}x^k=\frac{x^{n+1}-1}{x-1}

    • 結果の簡略化

      • =\frac{(3/16)^{\log_4n}-1}{(3/16)-1}cn^2 + θ(n^{\log_4{3}}) は一つ前の式の上界を∞にすると綺麗に整理できる｡
      • \sum_{i=3}^{\log_4{n-1}}(\frac{3}{16})^icn^2+θ(n^{\log_4{3}}) \lt \sum_{i=3}^{∞}(\frac{3}{16})^icn^2+θ(n^{\log_4{3}})
      • =\frac{1}{1-(3/16)}cn^2+θ(n^{\log_4{3}})※
      • =\frac{16}{13}cn^2+θ(n^{\log_4{3}})
      • =O(n^2)
        • ※P951無限減少幾何級数の変形規則(A.6)を適用している
          • \sum^∞_{k=0}x^k=\frac{1}{1-x}

再帰木の推定を置き換え法で検証

  • 再帰木での推定T(n)=O(n2)が漸化式T(n)=3T(\lfloor n/4 \rfloor) + θ(n^2)の上界であることを証明する

  • あるd > 0にたいしてT (n) ≤ dn^2を示す

    • T (n) ≤ 3T (\lfloor n/4 \rfloor) + cn^2
    • ≤ 3d\lfloor n/4 \rfloor^2 + cn^2
    • ≤ 3d(n/4)^2 + cn^2
    • =\frac{3}{16}dn^2+cn^2
    • ≤dn^2
      • d ≥ (16/13)cで成立する

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

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