はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー！

トップ > アルゴリズム > アルゴリズムイントロダクション第4章の個人まとめ

アルゴリズムイントロダクション第4章の個人まとめ

アルゴリズム 勉強メモ

はじめに

前回の続きをやっていきたいと思います。
www.hanachiru-blog.com

今回のテーマは「分割統治法」になります。

www.hanachiru-blog.com

分割統治法

分割統治では以下の3つの段階を適応して問題を再帰的に解いた。

分割：問題をいくつかの部分問題に分割する。
統治：部分問題を再帰的に解くことによって統治する。ただし部分問題のサイズが十分小さい場合は直接的な方法で解く。
結合：部分問題の解を組み合わせて元の問題の解を得る。

部分問題が再帰的に解く必要がある程度に大きい場合を再帰段階、再帰する必要がない程度に小さくなった場合に基底に到達するという。


分割統治法の実行時間は再帰方程式または漸化式で表現できることが多い。

T(n) = \begin{cases}\Theta(1) & n \leq cのとき\\aT(\frac{n}{b}) + D(n) + C(n) & それ以外\end{cases}


この漸化式を解く方法を3つ紹介する。

  • 置き換法
  • 再帰木法
  • マスター法

置き換え法

限界を測定し、その測定が正しいことを数学的帰納法を用いて証明する。

1. 解の形を推定する
2. 数学的機能法を用いて定数を求め，推定した解がうまく働くことを示す

例. T(n) = 2(T\lfloor n/2 \rfloor) + nの上界

１. 推定

T(n) = O(n \lg n)と推定

2. 数学的帰納法

任意の定数 c > 0に対して、 T(n) \leq cn \lg n であることを示せば良い。

f:id:hanaaaaaachiru:20211017175242p:plain
証明

あとは数学的帰納法の基底を示せばOK。

任意の n \geq n_0に対して、 T(n) \leq cn \lg nを証明できれば良いので、 n_0=2，T(2), T(3)を用いる。
また問題の条件が T(1)=1であるとする。

・ T(2) \leq c2 \lg 2
・ T(3) \leq c3 \lg 3

再帰木法

節点が再帰の各レベルで必要なコストを表現する木の形に漸化式を変形し、和を上または下から抑える技法を用いて漸化式を解く。

推定の道具として用いられることが多いが、細心の注意を払えば証明として利用可能。

f:id:hanaaaaaachiru:20211017232051p:plain
T(n) = 2T(n/2) + n^2

高さごとに値の和を求め、それの総和が実行時間になる。

高さ 和
0 f(n)
1 af(n/b)
2 a^2f(n/b^2)
... ...
i a^if(n/b^i)
... ...
\log_b n a^{\log_b n} (= n^{\log_b a})


例. T(n) = 3T(n/4) + \Theta (n^2)

T(n) = cn^2+ \frac{3}{16}cn^2 + ... + (\frac{3}{16})^{\log_4n-1}cn^2 + \Theta(n^{\log_43})
　 　 = \sum_{i=0}^{\log_4n-1}3^i c (\frac{n}{4^i})^2 + \Theta(n^{\log_43})
　 　 < \sum_{i=0}^{∞} (\frac{3}{16})^i cn^2 + \Theta(n^{\log_43})
　 　 = \frac{1}{1 - (3/16)} cn^2 + \Theta(n^{\log_43})
　 　 = \frac{16}{13} cn^2 + \Theta(n^{\log_43})
　　 = O (n^2)

マスター法

定数 a \geq1, b > 1と与えられた関数 f(x)によって

T(n) = aT(n/b) + f(n)

と表現できる漸化式に対して限界を与える。

マスター定理

1. \exists\epsilon > 0 \, s.t.\, f(n) = O(n^{\log_ba- \epsilon}) \Rightarrow T(n) = \Theta (n^{\log_b a})
2. f(n) = \Theta(n^{\log_ba}) \Rightarrow T(n) = \Theta (n^{\log_b a} \lg n)
3. \exists \epsilon > 0 \, s.t. \, f(n) =\Omega (n^{\log_b a + \epsilon}) \wedge \exists c < 1 \, s.t. \, \forall n : nが十分大きい , af(n/b) \leq cf(n) \Rightarrow T(n) = \Theta (f(n))


例1. T(n) = 9T(n/3) + n
マスター定理１において、 a = 9, b = 3, f(n) = nより n^{\log_ba} = n^{\log_39} = \Theta(n^2)
\epsilon = 1のとき仮定が満たされるので、 T(n) = \Theta(n^2)


例2. T(n) = T(2n/3) + 1
マスター定理２において、 a = 1, b = 3/2 , f(n) = 1より n^{\log_ba} = n^{\log_{3/2}1} = n^0 = 1
よって T(n) = \Theta(\log n )

例3. T(n) = 3T(n/4) + n \log n
マスター定理３のおいて、 a = 3, b = 4, f(n) = n \log nより n^{\log_ba} = n^{\log_43} = n^{0.793}
\epsilon = 0.2, c = 3/4のとき仮定が満たされるので、 T(n) = \Theta(n \log n)